IB Questionbank

HL Paper 3

Consider the recurrence relation $a{u_{n + 2}} + b{u_{n + 1}} + c{u_n} = 0,{\text{ }}n \in \mathbb{N}$ where $a$, $b$ and $c$ are constants. Let $\alpha $ and $\beta $ denote the roots of the equation $a{x^2} + bx + c = 0$.

Verify that the recurrence relation is satisfied by

\[{u_n} = A{\alpha ^n} + B{\beta ^n},\]

where $A$ and $B$ are arbitrary constants.

[4]

Solve the recurrence relation

${u_{n + 2}} - 2{u_{n + 1}} + 5{u_n} = 0$ given that ${u_0} = 0$ and ${u_1} = 4$.

[9]

Markscheme

attempt to substitute the given expression for ${u_n}$ into the recurrence relation M1

$a{u_{n + 2}} + b{u_{n + 1}} + c{u_n} = a(A{\alpha ^{n + 2}} + B{\beta ^{n + 2}}) + b(A{\alpha ^{n + 1}} + B{\beta ^{n + 1}}) + c(A{\alpha ^n} + B{\beta ^n})$ A1

$ = A{\alpha ^n}(a{\alpha ^2} + b\alpha + c) + B{\beta ^n}(a{\beta ^2} + b\beta + c)$ A1

$ = 0$ because $\alpha $ and $\beta $ both satisfy $a{x^2} + bx + c = 0$ R1AG

Note: Award M1A0A1R0 for solutions that are set to zero throughout and conclude with $0 = 0$. Award the R1 for any valid reason.

[4 marks]

the auxiliary equation is ${x^2} - 2x + 5 = 0$ A1

solving their quadratic equation (M1)

the roots are $1 \pm 2{\text{i}}$ A1

the general solution is

${u_n} = A{\left( {1 + 2{\text{i}}} \right)^n}{\mkern 1mu} + B{\left( {1 - 2{\text{i}}} \right)^n}{\mkern 1mu} {\mkern 1mu} {\mkern 1mu} \left( {{u_n} = {{\left( {\sqrt 5 } \right)}^n}\left( {A\,{\text{cis}}\left( {n\arctan 2} \right) + B\,{\text{cis}}\left( { - n\arctan 2} \right)} \right)} \right)$ (A1)

attempt to substitute both boundary conditions M1

$A + B = 0;{\text{ }}A(1 + 2{\text{i}}) + B(1 - 2{\text{i}}) = 4$ A1

attempt to solve their equations for $A$ and $B$ M1

$A = - {\text{i}},{\text{ }}B = {\text{i}}$ A1

${u_n} = {\text{i}}{(1 - 2{\text{i}})^n} - {\text{i}}{(1 + 2{\text{i}})^n}\,\,\,\left( {{u_n} = 2{{\left( {\sqrt 5 } \right)}^n}\sin (n\arctan 2)} \right)$ A1

Note: Accept the trigonometric form for ${u_n}$.

[9 marks]

Examiners report

[N/A]

Show that ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k - 1,\,2} \right)$, where $k \in {\mathbb{Z}^ + },\,k > 1$.

[4]

State the value of ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$ for odd positive integers $k$.

[1]

b.i.

State the value of ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$ for even positive integers $k$.

[1]

b.ii.

Markscheme

METHOD 1

attempting to use the Euclidean algorithm M1

$4k + 2 = 1\left( {3k + 1} \right) + \left( {k + 1} \right)$ A1

$3k + 1 = 2\left( {k + 1} \right) + \left( {k - 1} \right)$ A1

$K + 1 = \left( {k - 1} \right) + 2$ A1

$ = {\text{gcd}}\left( {k - 1,\,2} \right)$ AG

METHOD 2

${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$

$ = {\text{gcd}}\left( {4k + 2 - \left( {3k + 1} \right),\,3k + 1} \right)$ M1

$ = {\text{gcd}}\left( {3k + 1,\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{k + 1,}}\,{\text{3k + 1}}} \right)} \right)$ A1

$ = {\text{gcd}}\left( {3k + 1 - 2\left( {k + 1} \right),\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {k - 1{\text{,}}\,k + {\text{1}}} \right)} \right)$ A1

$ = {\text{gcd}}\left( {k + 1 - \left( {k - 1} \right),\,k - 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{2,}}\,k - {\text{1}}} \right)} \right)$ A1

$ = {\text{gcd}}\left( {k - 1,\,2} \right)$ AG

[4 marks]

(for $k$ odd), ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 2$ A1

[1 mark]

b.i.

(for $k$ even), ${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 1$ A1

[1 mark]

b.ii.

Examiners report

[N/A]

b.i.

[N/A]

b.ii.

The weights of the edges in the complete graph $G$ are given in the following table.

M17/5/MATHL/HP3/ENG/TZ0/DM/02

Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $G$.

[5]

By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for $G$.

[7]

Markscheme

the edges are traversed in the following order

AB A1

CF A1

ED A1

DA A1

${\text{upper bound}} = {\text{weight of this cycle}} = 4 + 1 + 2 + 7 + 11 + 8 = 33$ A1

[5 marks]

having deleted A, the order in which the edges are added is

BC A1

CF A1

CD A1

EF A1

Note: Accept indication of the correct order on a diagram.

to find the lower bound, we now reconnect A using the two edges with the lowest weights, that is AB and AF (M1)(A1)

${\text{lower bound}} = 1 + 2 + 5 + 7 + 4 + 6 = 25$ A1

Note: Award (M1)(A1)A1 for ${\text{LB}} = 15 + 4 + 6 = 25$ obtained either from an incorrect order of correct edges or where order is not indicated.

[7 marks]

Examiners report

[N/A]

Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.

The weighted graph $H$, representing the distances, measured in kilometres, between the five libraries, has the following table.

N17/5/MATHL/HP3/ENG/TZ0/DM/01

Draw the weighted graph $H$.

[2]

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

[5]

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

[4]

Markscheme

N17/5/MATHL/HP3/ENG/TZ0/DM/M/01.a

complete graph on 5 vertices A1

weights correctly marked on graph A1

[2 marks]

clear indication that the nearest-neighbour algorithm has been applied M1

DA (or 16) A1

AB (or 18) then BC (or 15) A1

CE (or 17) then ED (or 19) A1

${\text{UB}} = 85$ A1

[5 marks]

an attempt to find the minimum spanning tree (M1)

DA (16) then BE (17) then AB (18) (total 51) A1

reconnect C with the two edges of least weight, namely CB (15) and CE (17) M1

${\text{LB}} = 83$ A1

[4 marks]

Examiners report

[N/A]

A recurrence relation is given by ${u_{n + 1}} + 2{u_n} + 1 = 0,{\text{ }}{u_1} = 4$.

Use the recurrence relation to find ${u_2}$.

[1]

Find an expression for ${u_n}$ in terms of $n$.

[6]

A second recurrence relation, where ${v_1} = {u_1}$ and ${v_2} = {u_2}$, is given by ${v_{n + 1}} + 2{v_n} + {v_{n - 1}} = 0,{\text{ }}n \ge 2$.

Find an expression for ${v_n}$ in terms of $n$.

[6]

Markscheme

${u_2} = - 9$ A1

[1 mark]

METHOD 1

${u_{n + 1}} = - 2{u_n} - 1$

let ${u_n} = a{( - 2)^n} + b$ M1A1

EITHER

$a{( - 2)^{n + 1}} + b = - 2\left( {a{{( - 2)}^n} + b} \right) - 1$ M1

$a{( - 2)^{n + 1}} + b = a{( - 2)^{n + 1}} - 2b - 1$

$3b = - 1$

$b = - \frac{1}{3}$ A1

${u_1} = 4 \Rightarrow - 2a - \frac{1}{3} = 4$ (M1)

$ \Rightarrow a = - \frac{{13}}{6}$ A1

using ${u_1} = 4,{\text{ }}{u_2} = - 9$

$4 = - 2a + b,{\text{ }} - 9 = 4a + b$ M1A1

solving simultaneously M1

$ \Rightarrow a = - \frac{{13}}{6},{\text{ and }}b = - \frac{1}{3}$ A1

THEN

so ${u_n} = - \frac{{13}}{6}{( - 2)^n} - \frac{1}{3}$

METHOD 2

use of the formula ${u_n} = {a^n}{u_0} + b\left( {\frac{{1 - {a^n}}}{{1 - a}}} \right)$ (M1)

letting ${u_0} = - \frac{5}{2}$ A1

letting $a = - 2$ and $b = - 1$ A1

${u_n} = - \frac{5}{2}{( - 2)^n} - 1\left( {\frac{{1 - {{( - 2)}^n}}}{{1 - - 2}}} \right)$ M1A1

$ = - \frac{{13}}{6}{( - 2)^n} - \frac{1}{3}$ A1

[6 marks]

auxiliary equation is ${k^2} + 2k + 1 = 0$ M1

hence $k = - 1$ (A1)

so let ${v_n} = (an + b){( - 1)^n}$ M1

$(2a + b){( - 1)^2} = - 9$ and $(a + b){( - 1)^1} = 4$ A1

so $a = - 5,{\text{ }}b = 1$ M1A1

${v_n} = (1 - 5n){( - 1)^n}$

Note: Caution necessary to allow FT from (a) to part (c).

[6 marks]

Total [13 marks]

Examiners report

[N/A]

Consider ${\kappa _n}$, a complete graph with $n$ vertices, $n \geqslant 2$. Let $T$ be a fixed spanning tree of ${\kappa _n}$.

Draw the complete bipartite graph ${\kappa _{3,3}}$.

[1]

a.i.

Prove that ${\kappa _{3,3}}$ is not planar.

[4]

a.ii.

A connected graph $G$ has $v$ vertices. Prove, using Euler’s relation, that a spanning tree for $G$ has $v - 1$ edges.

[2]

If an edge $E$ is chosen at random from the edges of ${\kappa _n}$, show that the probability that $E$ belongs to $T$ is equal to $\frac{2}{n}$.

[4]

Markscheme

N17/5/MATHL/HP3/ENG/TZ0/DM/M/03.a.i A1

[1 mark]

a.i.

assume ${\kappa _{3,3}}$ is planar

${\kappa _{3,3}}$ has no cycles of length 3 R1

use of $e \leqslant 2v - 4$ M1

$e = 9$ and $v = 6$ A1

hence inequality not satisfied 9 $\not \leqslant $ 8 R1

so ${\kappa _{3,3}}$ is not planar AG

Note: use of $e \leqslant 3v - 6$ with $e = 9$ and $v = 6$ and concluding that this inequality does not show whether ${\kappa _{3,3}}$ is planar or not just gains R1.

[4 marks]

a.ii.

a spanning tree (is planar and) has one face A1

Euler’s relation is $v - e + f = 2$

$v - e + 1 = 2$ M1

$ \Rightarrow e = v - 1$ AG

[2 marks]

${\kappa _n}$ has $\left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right)$ edges $\left( {\frac{{n(n - 1)}}{2}{\text{ edges}}} \right)$ (A1)

${\text{P}}(E{\text{ belongs to }}T) = \frac{{n - 1}}{{\left( {\frac{{n(n - 1)}}{2}} \right)}}$ M1A1

clear evidence of simplification of the above expression M1

$ = \frac{2}{n}$ AG

[4 marks]

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

The simple, complete graph ${\kappa _n}(n > 2)$ has vertices ${{\text{A}}_1},{\text{ }}{{\text{A}}_2},{\text{ }}{{\text{A}}_3},{\text{ }} \ldots ,{\text{ }}{{\text{A}}_n}$. The weight of the edge from ${{\text{A}}_i}$ to ${{\text{A}}_j}$ is given by the number $i + j$.

Consider the general graph ${\kappa _n}$.

(i) Draw the graph ${\kappa _4}$ including the weights of all the edges.

(ii) Use the nearest-neighbour algorithm, starting at vertex ${{\text{A}}_1}$, to find a Hamiltonian cycle.

(iii) Hence, find an upper bound to the travelling salesman problem for this weighted graph.

[4]

Consider the graph ${\kappa _5}$. Use the deleted vertex algorithm, with ${{\text{A}}_5}$ as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

[5]

(i) Use the nearest-neighbour algorithm, starting at vertex ${{\text{A}}_1}$, to find a Hamiltonian cycle.

(ii) Hence find and simplify an expression in $n$, for an upper bound to the travelling salesman problem for this weighted graph.

[7]

By splitting the weight of the edge ${{\text{A}}_i}{{\text{A}}_j}$ into two parts or otherwise, show that all Hamiltonian cycles of ${\kappa _n}$ have the same total weight, equal to the answer found in (c)(ii).

[3]

Markscheme

(i) N16/5/MATHL/HP3/ENG/TZ/DM/M/04.a A1A1

Note: A1 for the graph, A1 for the weights.

(ii) cycle is ${{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3}{{\text{A}}_4}{{\text{A}}_1}$ A1

(iii) upper bound is $3 + 5 + 7 + 5 = 20$ A1

[4 marks]

with ${{\text{A}}_5}$ deleted, (applying Kruskal’s Algorithm) the minimum spanning tree will consist of the edges ${{\text{A}}_1}{{\text{A}}_2},{\text{ }}{{\text{A}}_1}{{\text{A}}_3}{\text{, }}{{\text{A}}_1}{{\text{A}}_4}$, of weights 3, 4, 5 (M1)A1

the two edges of smallest weight from ${{\text{A}}_5}$ are ${{\text{A}}_5}{{\text{A}}_1}$ and ${{\text{A}}_5}{{\text{A}}_2}$ of weights 6 and 7 (M1)A1

so lower bound is $3 + 4 + 5 + 6 + 7 = 25$ A1

[5 marks]

(i) starting at ${{\text{A}}_1}$ we go ${{\text{A}}_2},{\text{ }}{{\text{A}}_3}{\text{ }} \ldots {\text{ }}{{\text{A}}_n}$

we now have to take ${{\text{A}}_n}{{\text{A}}_1}$

thus the cycle is ${{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3} \ldots {{\text{A}}_{n - 1}}{{\text{A}}_n}{{\text{A}}_1}$ A1A1

Note: Final A1 is for ${{\text{A}}_n}{{\text{A}}_1}$.

(ii) smallest edge from ${{\text{A}}_1}$ is ${{\text{A}}_1}{{\text{A}}_2}$ of weight 3, smallest edge from ${{\text{A}}_2}$ (to a new vertex) is ${{\text{A}}_2}{{\text{A}}_3}$ of weight 5, smallest edge from ${{\text{A}}_{n - 1}}$ (to a new vertex) is ${{\text{A}}_{n - 1}}{{\text{A}}_n}$ of weight $2n - 1$ (M1)

weight of ${{\text{A}}_n}{{\text{A}}_1}$ is $n + 1$

weight is $3 + 5 + 7 + \ldots + (2n - 1) + (n + 1)$ A1

$ = \frac{{(n - 1)}}{2}(2n + 2) + (n + 1)$ M1A1

$ = n(n + 1)$ (which is an upper bound) A1

Note: Follow through is not applicable.

[7 marks]

put a marker on each edge ${{\text{A}}_i}{{\text{A}}_j}$ so that $i$ of the weight belongs to vertex ${{\text{A}}_i}$ and $j$ of the weight belongs to vertex ${{\text{A}}_j}$ M1

the Hamiltonian cycle visits each vertex once and only once and for vertex ${{\text{A}}_i}$ there will be weight $i$ (belonging to vertex ${{\text{A}}_i}$) both going in and coming out R1

so the total weight will be $\sum\limits_{i = 1}^n {2i = 2\frac{n}{2}(n + 1) = n(n + 1)} $ A1AG

Note: Accept other methods for example induction.

[3 marks]

Examiners report

[N/A]

In this question the notation ${({a_n}{a_{n - 1}} \ldots {a_2}{a_1}{a_0})_b}$ is used to represent a number in base $b$, that has unit digit of ${a_0}$. For example ${(2234)_5}$ represents $2 \times {5^3} + 2 \times {5^2} + 3 \times 5 + 4 = 319$ and it has a unit digit of 4.

Let $x$ be the cube root of the base 7 number ${(503231)_7}$.

(i) By converting the base 7 number to base 10, find the value of $x$, in base 10.

(ii) Express $x$ as a base 5 number.

[7]

Let $y$ be the base 9 number ${({a_n}{a_{n - 1}} \ldots {a_1}{a_0})_9}$. Show that $y$ is exactly divisible by 8 if and only if the sum of its digits, $\sum\limits_{i = 0}^n {{a_i}} $, is also exactly divisible by 8.

[7]

Using the method from part (b), find the unit digit when the base 9 number ${(321321321)_9}$ is written as a base 8 number.

[3]

Markscheme

(i) converting to base 10

${(503231)_7} = 5 \times {7^5} + 3 \times {7^3} + 2 \times {7^2} + 3 \times 7 + 1 = 85184$ M1A1A1

so $x = 44$ A1

(ii) repeated division by 5 gives (M1)

N16/5/MATHL/HP3/ENG/TZ/DM/M/01.a

so base 5 value for $x$ is ${(134)_5}$ A1

Notes: Alternative method is to successively subtract the largest multiple of 25 and then 5.

Follow through if they forget to take the cube root and obtain ${(10211214)_5}$ then award (M1)(A1)A1.

[7 marks]

$9 \equiv 1(\bmod 8)$ A1

${9^i} \equiv {1^i} \equiv 1(\bmod 8)$ $i \in \mathbb{N}$ (M1)(A1)

$y = {a_n}{9^n} + {a_{n - 1}}{9^{n - 1}} + \ldots + {a_1}9 + {a_0} \equiv {a_n}{1^n} + {a_{n - 1}}{1^{n - 1}} + \ldots + {a_1}1 + {a_0} \equiv $

${a_n} + {a_{n - 1}} + \ldots + {a_1} + {a_0} \equiv \sum\limits_{i = 0}^n {{a_i}(\bmod 8)} $ M1A1A1

so $y = 0(\bmod 8)$ and hence divisible by 8 if and only if $\sum\limits_{i = 0}^n {{a_i} \equiv 0(\bmod 8)} $ and hence divisible by 8 R1AG

Note: Accept alternative valid methods eg binomial expansion of ${(8 + 1)^i}$, factorization of $({a^i} - 1)$ if they have sufficient explanation.

[7 marks]

using part (b), ${(321321321)_9} \equiv 3 + 2 + 1 + 3 + 2 + 1 + 3 + 2 + 1 = 18 \equiv 2(\bmod 8)$ M1A1

so the unit digit is 2 A1

[3 marks]

Examiners report

[N/A]

Consider the system of linear congruences

\[\begin{array}{*{20}{l}} {x \equiv 2(\bmod 5)} \\ {x \equiv 5(\bmod 8)} \\ {x \equiv 1(\bmod 3).} \end{array}\]

With reference to the integers 5, 8 and 3, state why the Chinese remainder theorem guarantees a unique solution modulo 120 to this system of linear congruences.

[2]

Hence or otherwise, find the general solution to the above system of linear congruences.

[7]

Markscheme

5, 8 and 3 are pairwise relatively prime (or equivalent) R1

120 is the product of 5, 8 and 3 R1

[2 marks]

METHOD 1

$x = 2 + 5t,{\text{ }}t \in \mathbb{Z}$ and $2 + 5t \equiv 5(\bmod 8)$ M1

$5t \equiv 3(\bmod 8) \Rightarrow 5t \equiv 35(\bmod 8)$ (M1)

$t = 7 + 8u,{\text{ }}u \in \mathbb{Z}$ (A1)

$x = 2 + 5(7 + 8u) \Rightarrow x = 37 + 40u$ (A1)

$37 + 40u \equiv 1(\bmod 3) \Rightarrow u \equiv 0(\bmod 3)$ (A1)

$u = 3v,{\text{ }}v \in \mathbb{Z}$ (A1)

$x = 37 + 40(3v)$

$x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)$ A1

METHOD 2

attempting systematic listing of possibilities M1

solutions to $x \equiv 2(\bmod 5)$ are $x = 2,{\text{ }}7,{\text{ }}12,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots $ (A1)

solutions to $x \equiv 5(\bmod 8)$ are $x = 5,{\text{ }}13,{\text{ }}21,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots $ (A1)

solutions to $x \equiv 1(\bmod 3)$ are $x = 1,{\text{ }}4,{\text{ }}7,{\text{ }} \ldots ,{\text{ }}37,{\text{ }} \ldots $ (A1)

a solution is $x = 37$ (A1)

using the Chinese remainder theorem (M1)

$x = 37 + 120v{\text{ }}\left( {x \equiv 37(\bmod 120)} \right)$ A1

METHOD 3

attempting to find ${M_i},{\text{ }}i = 1,{\text{ }}2,{\text{ 3}}$

${M_1} = 8 \times 3 = 24,{\text{ }}{M_2} = 5 \times 3 = 15$ and ${M_3} = 5 \times 8 = 40$ M1

using ${M_i}{x_i} \equiv 1(\bmod {m_i}),{\text{ }}i = 1,{\text{ }}2,{\text{ }}3$ to obtain

$24{x_1} \equiv 1(\bmod 5),{\text{ }}15{x_2} \equiv 1(\bmod 8)$ and $40{x_3} \equiv 1(\bmod 3)$ M1

${x_1} \equiv 4(\bmod 5),{\text{ }}{x_2} \equiv 7(\bmod 8)$ and ${x_3} \equiv 1(\bmod 3)$ (A1)(A1)(A1)

use of $x \equiv {a_1}{x_1}{M_1} + {a_2}{x_2}{M_2} + {a_3}{x_3}{M_3}(\bmod M)$ gives

$x = (2 \times 4 \times 24 + 5 \times 7 \times 15 + 1 \times 1 \times 40)(\bmod 120)$ (M1)

$x \equiv 757(\bmod 120){\text{ }}\left( { \equiv 37(\bmod 120)} \right){\text{ }}(x = 37 + 120v,{\text{ }}v \in \mathbb{Z})$ A1

[7 marks]

Examiners report

[N/A]

In this question no graphs are required to be drawn. Use the handshaking lemma and other results about graphs to explain why,

a graph cannot exist with a degree sequence of $1,{\text{ }}2,{\text{ }}3,{\text{ }}4,{\text{ }}5,{\text{ }}6,{\text{ }}7,{\text{ }}8,{\text{ }}9$;

[2]

a simple, connected, planar graph cannot exist with a degree sequence of $4,{\text{ }}4,{\text{ }}4,{\text{ }}4,{\text{ }}5,{\text{ }}5$;

[3]

a tree cannot exist with a degree sequence of $1,{\text{ }}1,{\text{ }}2,{\text{ }}2,{\text{ }}3,{\text{ }}3$.

[3]

Markscheme

assume such a graph exists

by the handshaking lemma the sum of the degrees equals twice the number of edges R1

but $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$ which is odd R1

this is a contradiction so graph does not exist AG

[2 marks]

assume such a graph exists

since the graph is simple and connected (and $v = 6 > 2$) then $e \leqslant 3v - 6$ R1

by the handshaking lemma $4 + 4 + 4 + 4 + 5 + 5 = 2e$ so $e = 13$ A1

hence $13 \leqslant 3 \times 6 - 6 = 12$ A1

this is a contradiction so graph does not exist AG

[3 marks]

assume such a graph exists

a tree with 6 vertices must have 5 edges (since ${\text{V}} - {\text{E}} + 1 = 2$ for a tree) R1

using the Handshaking Lemma $1 + 1 + 2 + 2 + 3 + 3 = 2 \times 5$ implies $12 = 10$ M1A1

this is a contradiction so graph does not exist AG

[3 marks]

Examiners report

[N/A]

The distances by road, in kilometres, between towns in Switzerland are shown in the following table.

A cable television company wishes to connect the six towns placing cables along the road system.

Use Kruskal’s algorithm to find the minimum length of cable needed to connect the six towns.

[5]

Visitors to Switzerland can visit some principal locations for tourism by using a network of scenic railways as represented by the following graph:

(i) State whether the graph has any Hamiltonian paths or Hamiltonian cycles, justifying your answers.

(ii) State whether the graph has any Eulerian trails or Eulerian circuits, justifying your answers.

(iii) The tourist board would like to make it possible to arrive in Geneva, travel all the available scenic railways, exactly once, and depart from Zurich. Find which locations would need to be connected by a further scenic railway in order to make this possible.

[6]

Markscheme

Zurich-Basel 85 M1A1

Berne-Basel 100 A1

Sion-Berne 155

Sion-Geneva 160

Zurich-Lugano 210 A1

total length of pipe needed is 710 km A1

Note: Award M1 for attempt to start with smallest length.

Note: Accept graphical solution showing lengths chosen.

Note: Award N1 for a correct spanning tree and N1 for 710 km with no method shown.

[6 marks]

(i) possible Hamiltonian path eg Geneva-Montreux-Zermatt-Lugano-St Moritz-Interlaken-Luzern-Zurich-Berne A1

no possible Hamiltonian cycles eg we would have to pass through Montreux twice as Geneva is only connected to Montreux or Interlaken twice R1

(ii) possible Eulerian trail as there are 2 odd vertices (Geneva and St Moritz) R1

no possible Eulerian circuits as not all even vertices R1

Note: Accept an example of a Eulerian trail for the first R1.

(iii) St Moritz to Zurich A2

Note: If St Moritz and Zurich are connected via existing edges award A1.

[6 marks]

Total [11 marks]

Examiners report

[N/A]

In a computer game, Fibi, a magic dragon, is climbing a very large staircase. The steps are labelled 0, 1, 2, 3 … .

She starts on step 0. If Fibi is on a particular step then she can either jump up one step or fly up two steps. Let ${u_n}$ represent the number of different ways that Fibi can get to step $n$. When counting the number of different ways, the order of Fibi’s moves matters, for example jump, fly, jump is considered different to jump, jump, fly. Let ${u_0} = 1$.

Find the values of ${u_1},{\text{ }}{u_2},{\text{ }}{u_3}$.

[3]

Show that ${u_{n + 2}} = {u_{n + 1}} + {u_n}$.

[2]

(i) Write down the auxiliary equation for this recurrence relation.

(ii) Hence find the solution to this recurrence relation, giving your answer in the form ${u_n} = A{\alpha ^n} + B{\beta ^n}$ where $\alpha $ and $\beta $ are to be determined exactly in surd form and $\alpha > \beta $. The constants $A$ and $B$ do not have to be found at this stage.

[5]

(i) Given that $A = \frac{1}{{\sqrt 5 }}\left( {\frac{{1 + \sqrt 5 }}{2}} \right)$, use the value of ${u_0}$ to determine $B$.

(ii) Hence find the explicit formula for ${u_n}$.

[3]

Find the value of ${u_{20}}$.

[1]

Find the smallest value of $n$ for which ${u_n} > 100\,000$.

[2]

Markscheme

${u_1} = 1,{\text{ }}{u_2} = 2,{\text{ }}{u_3} = 3$ A1A1A1

[3 marks]

to get to step $n + 2$ she can either fly from step $n$ or jump from step $n + 1$ R2

so ${u_{n + 2}} = {u_{n + 1}} + {u_n}$ AG

[2 marks]

(i) auxiliary equation ${\lambda ^2} - \lambda - 1 = 0$ M1A1

Note: Award M1 for attempting to write down a relevant quadratic.

(ii) $\lambda = \frac{{1 \pm \sqrt {1 + 4} }}{2}$ M1A1

${u_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^n}$ A1

[5 marks]

(i) ${u_0} = 1$ implies $A + B = 1$. So $B = - \frac{1}{{\sqrt 5 }}\left( {\frac{{1 - \sqrt 5 }}{2}} \right)$ M1A1

(ii) ${u_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^{n + 1}} - \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^{n + 1}}$ A1

Note: Accept equivalent expressions in parts (i) and (ii).

[3 marks]

${u_{20}} = 10946$ A1

[1 mark]

using table, smallest value for $n$ is 25 (gives 121393) (M1)A1

Note: Accept other methods, eg, logs on the dominant term.

[2 marks]

Examiners report

[N/A]

Use the result $2003 = 6 \times 333 + 5$ and Fermat’s little theorem to show that ${2^{2003}} \equiv 4(\bmod 7)$ .

[3]

Find ${2^{2003}}(\bmod 11)$ and ${2^{2003}}(\bmod 13)$.

[3]

Use the Chinese remainder theorem, or otherwise, to evaluate ${2^{2003}}(\bmod 1001)$, noting that $1001 = 7 \times 11 \times 13$.

[7]

Markscheme

${2^{2003}} = {2^5} \times {({2^6})^{333}}$ M1A1

$ \equiv 32 \times 1(\bmod 7)$ by Fermat’s little theorem A1

$ \equiv 4(\bmod 7)$ AG

[3 marks]

$2003 = 3 + 10 \times 200$ (M1)

${2^{2003}} = {2^3} \times {({2^{10}})^{200}}\left( { \equiv 8 \times 1(\bmod 11)} \right) \equiv 8(\bmod 11)$ A1

${2^{2003}} = {2^{11}} \times {({2^{12}})^{166}} \equiv 7(\bmod 13)$ A1

[3 marks]

form ${M_1} = \frac{{1001}}{7} = 143;{\text{ }}{M_2} = \frac{{1001}}{{11}} = 91;{\text{ }}{M_3} = \frac{{1001}}{{13}} = 77$ M1

solve $143{x_1} \equiv 1(\bmod 7) \Rightarrow {x_1} = 5$ M1A1

${x_2} = 4;{\text{ }}{x_3} = 12$ A1A1

$x = 4 \times 143 \times 5 + 8 \times 91 \times 4 + 7 \times 77 \times 12 = 12240 \equiv 228(\bmod 1001)$ M1A1

[7 marks]

Examiners report

Many candidates were able to complete part (a) and then went on to part (b). Some candidates raced through part (c). Others, who attempted part (c) using the alternative strategy of repeatedly solving linear congruencies, were sometimes successful.

Let the greatest common divisor of 861 and 957 be h .

Using the Euclidean algorithm, find h .

[4]

Hence find integers A and B such that 861A + 957B = h .

[3]

Using part (b), solve $287w \equiv 2(\bmod 319$) , where $w \in \mathbb{N},{\text{ }}w < 319$ .

[5]

Find the general solution to the diophantine equation $861x + 957y = 6$ .

[6]

Markscheme

METHOD 1

by the above working on the left (or similar) M1A1A1

Note: Award A1 for 96 and A1 for 93.

h = 3 (since 3 divides 93) A1

[4 marks]

METHOD 2

$957 = 861 + 96$ M1A1

$861 = 8 \times 96 + 93$ A1

$96 = 93 + 3$

so h = 3 (since 3 divides 93) A1

[4 marks]

METHOD 1

if method 1 was used for part (a)

by the above working on the right (or equivalent) M1

$ - 10 \times 861 + 9 \times 957 = 3$

so A = –10 and B = 9 A1A1

[3 marks]

METHOD 2

$3 = 96 - 93$

$ = 96 - (861 - 8 \times 96) = 9 \times 96 - 861$ M1

$ = 9 \times (957 - 861) - 861$

$ = - 10 \times 861 + 9 \times 957$

so A = –10 and B = 9 A1A1

[3 marks]

from (b) $ - 10 \times 287 + 9 \times 319 = 1$ so A1

$ - 10 \times 287 \equiv 1(\bmod 319)$ A1

$287w \equiv 2(\bmod 319) \Rightarrow - 10 \times 287w \equiv - 10 \times 2(\bmod 319)$ M1

$ \Rightarrow w \equiv - 20(\bmod 319)$ A1

so $w = 299$ A1

[5 marks]

from (b) $ - 10 \times 861 + 9 \times 957 = 3 \Rightarrow - 20 \times 861 + 18 \times 957 = 6$ M1A1

so general solution is $x = - 20 + 319t$ A1A1

$y = 18 - 287t\,\,\,\,\,(t \in \mathbb{Z})$ A1A1

[6 marks]

Examiners report

The Euclidean algorithm was well applied. If it is done in the format shown in the mark scheme then the keeping track method of the linear combinations of the 2 original numbers makes part (b) easier.

Again well answered but not quite as good as (a).

Surprisingly, since it is basic bookwork, this part was answered very badly indeed. Most candidates did not realise that $ - 10$ was the number to multiply by. Sadly, of the candidates that did do it, some did not read the question carefully enough to see that a positive integer answer was required.

Again this is standard bookwork. It was answered better than part (c). There were the usual mistakes in the final answer e.g. not having the two numbers, with the parameter, co-prime.

Consider the following weighted graph G.

State what feature of G ensures that G has an Eulerian trail.

[1]

a.i.

State what feature of G ensures that G does not have an Eulerian circuit.

[1]

a.ii.

Write down an Eulerian trail in G.

[2]

State the Chinese postman problem.

[2]

c.i.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

[3]

c.ii.

Calculate the total weight of the solution.

[1]

c.iii.

Markscheme

G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree R1

[1 mark]

a.i.

G does not have an Eulerian circuit because not all vertices are of even degree R1

[1 mark]

a.ii.

for example BAEBCEFCDF A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

to determine the shortest route (walk) around a weighted graph A1

using each edge (at least once, returning to the starting vertex) A1

Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.

[2 marks]

c.i.

we require the Eulerian trail in (b), (weight = 65) (M1)

and the minimum walk FEB (15) A1

for example BAEBCEFCDFEB A1

Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

[3 marks]

c.ii.

total weight is (65 + 15=)80 A1

[1 mark]

c.iii.

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

c.i.

[N/A]

c.ii.

[N/A]

c.iii.

The simple, connected graph $G$ has e edges and $v$ vertices, where $v \geqslant 3$.

Given that both $G$ and $G'$ are planar and connected,

Show that the number of edges in $G'$, the complement of $G$, is $\frac{1}{2}{v^2} - \frac{1}{2}v - e$.

[2]

show that the sum of the number of faces in $G$ and the number of faces in $G'$ is independent of $e$;

[3]

show that ${v^2} - 13v + 24 \leqslant 0$ and hence determine the maximum possible value of $v$.

[7]

Markscheme

the total number of edges in $G$ and $G'$ is $\frac{{v(v - 1)}}{2}$ (A1)

the number of edges in $G' = \frac{{v(v - 1)}}{2} - e$ A1

$ = \frac{1}{2}{v^2} - \frac{1}{2}v - e$ AG

[2 marks]

using Euler’s formula, number of faces in $G = e + 2 - v$ A1

number of faces in $G' = \frac{{{v^2}}}{2} - \frac{v}{2} - e + 2 - v$ A1

sum of these numbers $ = \frac{{{v^2}}}{2} - \frac{{5v}}{2} + 4$ A1

this is independent of $e$ AG

[3 marks]

for $G$ to be planar, we require (M1)

$e \leqslant 3v - 6$ A1

for $e \leqslant 3v - 6$ to be planar, we require

$\frac{{{v^2}}}{2} - \frac{v}{2} - e \leqslant 3v - 6$ A1

for these two inequalities to be satisfied simultaneously, adding or substituting we require

$\frac{{{v^2}}}{2} - \frac{v}{2} \leqslant 6v - 12$ (M1)A1

leading to ${v^2} - 13v + 24 \leqslant 0$ AG

the roots of the equation are 10.8 (and 2.23) (A1)

the largest value of $v$ is therefore 10 A1

[7 marks]

Examiners report

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(a) If they considered the complete graph they were fine.

(b) Some confusion here if they were not clear about which graph they were applying Euler’s formula to. If they were methodical with good notation they obtained the answer.

(c) Again the same confusion about applying the inequality to both graphs. Most candidates realised which inequality was applicable. Many candidates had the good exam technique to pick up the last two marks even if they did not obtain the quadratic inequality.

The Fibonacci sequence can be described by the recurrence relation ${f_{n + 2}} = {f_{n + 1}} + {f_n}$ where ${f_0} = 0,\,{f_1} = 1$.

Write down the auxiliary equation and use it to find an expression for ${f_n}$ in terms of $n$.

[7]

It is known that ${\alpha ^2} = \alpha + 1$ where $\alpha = \frac{{1 + \sqrt 5 }}{2}$.

For integers $n$ ≥ 3, use strong induction on the recurrence relation ${f_{n + 2}} = {f_{n + 1}} + {f_n}$ to prove that ${f_n} > {\alpha ^{n - 2}}$.

[8]

Markscheme

attempt to find the auxiliary equation (${\lambda ^2} - \lambda - 1 = 0$) M1

$\lambda = \frac{{1 \pm \sqrt 5 }}{2}$ (A1)

the general solution is ${f_n} = A{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} + B{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^n}$ (M1)

imposing initial conditions (substituting $n$ = 0,1) M1

A + B = 0 and $A\left( {\frac{{1 + \sqrt 5 }}{2}} \right) + B\left( {\frac{{1 - \sqrt 5 }}{2}} \right) = 1$ A1

$A = \frac{1}{{\sqrt 5 }},\,\,B = - \frac{1}{{\sqrt 5 }}$ A1

${f_n} = \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 + \sqrt 5 }}{2}} \right)^n} - \frac{1}{{\sqrt 5 }}{\left( {\frac{{1 - \sqrt 5 }}{2}} \right)^n}$ A1

Note: Condone use of decimal numbers rather than exact answers.

[7 marks]

let P($n$) be ${f_n} > {\alpha ^{n - 2}}$ for integers $n$ ≥ 3

consideration of two consecutive values of $f$ R1

${f_3} = 2$ and ${\alpha ^{3 - 2}} = \frac{{1 + \sqrt 5 }}{2}\left( {1.618 \ldots } \right) \Rightarrow {\text{P}}\left( 3 \right)$ is true A1

${f_4} = 3$ and ${\alpha ^{4 - 2}} = \frac{{3 + \sqrt 5 }}{2}\left( {2.618 \ldots } \right) \Rightarrow {\text{P}}\left( 4 \right)$ is true A1

Note: Do not award A marks for values of $n$ other than $n$ = 3 and $n$ = 4.

(for $k$ ≥ 4), assume that P($k$) and P($k$ − 1) are true M1

required to prove that P($k$ + 1) is true

Note: Accept equivalent notation. Needs to start with 2 general consecutive integers and then prove for the next integer. This will affect the powers of the alphas.

${f_{k + 1}} = {f_k} + {f_{k - 1}}$ (and ${f_k} > {\alpha ^{k - 2}},\,{f_{k - 1}} > {\alpha ^{k - 3}}$) M1

${f_{k + 1}} > {\alpha ^{k - 2}} + {\alpha ^{k - 3}} = {\alpha ^{k - 3}}\left( {\alpha + 1} \right)$ A1

$ = {\alpha ^{k - 3}}{\alpha ^2} = {\alpha ^{k - 1}} = {\alpha ^{\left( {k + 1} \right) - 2}}$ A1

as P(3) and P(4) are true, and P($k$) , P($k$ − 1) true ⇒ P($k$ + 1) true then P($k$) is true for $k$ ≥ 3 by strong induction R1

Note: To obtain the final R1, at least five of the previous marks must have been awarded.

[8 marks]

Examiners report

[N/A]

Use the Euclidean Algorithm to find the greatest common divisor of 7854 and 3315.

Hence state the number of solutions to the diophantine equation 7854x + 3315y = 41 and justify your answer.

Markscheme

$7854 = 2 \times 3315 + 1224$ M1A1

$3315 = 2 \times 1224 + 867$ A1

$1224 = 1 \times 867 + 357$

$867 = 2 \times 357 + 153$

$357 = 2 \times 153 + 51$

$153 = 3 \times 51$ A1

The gcd is 51. A1

Since 51 does not divide 41, R1

there are no solutions. A1

[7 marks]

Examiners report

Most candidates were able to use the Euclidean Algorithm correctly to find the greatest common divisor. Candidates who used the GCD button on their calculators were given no credit. Some candidates seemed unaware of the criterion for the solvability of Diophantine equations.

Consider the recurrence relation

${u_n} = 5{u_{n - 1}} - 6{u_{n - 2}},{\text{ }}{u_0} = 0$ and ${u_1} = 1$.

Find an expression for ${u_n}$ in terms of $n$.

[6]

For every prime number $p > 3$, show that $p|{u_{p - 1}}$.

[4]

Markscheme

the auxiliary equation is ${\lambda ^2} - 5\lambda + 6 = 0$ M1

$ \Rightarrow \lambda = 2,{\text{ }}3$ (A1)

the general solution is ${u_n} = A \times {2^n} + B \times {3^n}$ A1

imposing initial conditions (substituting $n = 0,{\text{ }}1$) M1

$A + B = 0$ and $2A + 3B = 1$ A1

the solution is $A = - 1,{\text{ }}B = 1$

so that ${u_n} = {3^n} - {2^n}$ A1

[6 marks]

${u_{p - 1}} = {3^{p - 1}} - {2^{p - 1}}$

$p > 3$, therefore 3 or 2 are not divisible by $p$ R1

hence by FLT, ${3^{p - 1}} \equiv 1 \equiv {2^{p - 1}}(\bmod p)$ for $p > 3$ M1A1

${u_{p - 1}} \equiv 0(\bmod p)$ A1

$p|{u_{p - 1}}$ for every prime number $p > 3$ AG

[4 marks]

Examiners report

[N/A]

The decimal number 1071 is equal to $a$060 in base $b$, where $a > 0$.

Convert the decimal number 1071 to base 12.

[3]

Write the decimal number 1071 as a product of its prime factors.

[1]

Using your answers to part (a) and (b), prove that there is only one possible value for $b$ and state this value.

[4]

c.i.

Hence state the value of $a$.

[1]

c.ii.

Markscheme

EITHER

using a list of relevant powers of 12: 1, 12, 144 (M1)

$1071 = 7 \times {12^2} + 5 \times {12^1} + 3 \times {12^0}$ (A1)

attempted repeated division by 12 (M1)

$1071 \div 12 = 89{\text{rem}}3;{\text{ }}89 \div 12 = 7{\text{rem}}5$ (A1)

THEN

$1071 = {753_{12}}$ A1

[3 marks]

$1071 = 3 \times 3 \times 7 \times 17$ A1

[1 mark]

in base $b$ $a060$ ends in a zero and so $b$ is a factor of 1071 R1

from part (a) $b < 12$ as $a060$ has four digits and so the possibilities are

$b = 3,{\text{ }}b = 7$ or $b = 9$ R1

stating valid reasons to exclude both $b = 3$ eg, there is a digit of 6

and $b = 9$ eg, $1071 = {(1420)_9}$ R1

$b = 7$ A1

Note: The A mark is independent of the R marks.

[4 marks]

c.i.

$1071 = {(3060)_7} \Rightarrow a = 3$ A1

[1 mark]

c.ii.

Examiners report

[N/A]

c.i.

[N/A]

c.ii.

Use the Euclidean algorithm to find the greatest common divisor of 264 and 1365.

[5]

Hence, or otherwise, find the general solution of the Diophantine equation

\[264x - 1365y = 3.\]

[6]

b.i.

Hence find the general solution of the Diophantine equation

\[264x - 1365y = 6.\]

[2]

b.ii.

By expressing each of 264 and 1365 as a product of its prime factors, determine the lowest common multiple of 264 and 1365.

[3]

Markscheme

$1365 = 5 \times 264 + 45$ M1

$264 = 5 \times 45 + 39$ A1

$45 = 1 \times 39 + 6$ A1

$39 = 6 \times 6 + 3$

$6 = 2 \times 3$ A1

so gcd is 3

[5 marks]

EITHER

$39 - 6 \times 6 = 3$ (M1)

$39 - 6 \times (45 - 39) = 3 \Rightarrow 7 \times 39 - 6 \times 45 = 3$ (A1)

$7 \times (264 - 5 \times 45) - 6 \times 45 = 3 \Rightarrow 7 \times 264 - 41 \times 45 = 3$ (A1)

$7 \times 264 - 41 \times (1365 - 5 \times 264) = 3 \Rightarrow 212 \times 264 - 41 \times 1365 = 3$ (A1)

tracking the linear combinations when applying the Euclidean algorithm (could be displayed in (a))

M17/5/MATHL/HP3/ENG/TZ0/DM/M/01.b.i

THEN

a solution is $x = 212,y = 41$ (or equivalent eg $x = - 243,y = - 47$) (A1)

$x = 212 + 455N,y = 41 + 88N$ (or equivalent) $(N \in \mathbb{Z})$ A1

[6 marks]

b.i.

a solution is $x = 424,y = 82{\text{ }}({\text{or equivalent }}eg{\text{ }}x = - 31,{\text{ }}y = - 6)$ (A1)

$x = 424 + 455N,{\text{ }}y = 82 + 88N({\text{or equivalent}}){\text{ }}\left( {N \in \mathbb{Z}} \right)$ A1

Note: Award A1A0 for $x = 424 + 910N,{\text{ }}y = 82 + 176N$.

[2 marks]

b.ii.

$264 = 2 \times 2 \times 2 \times 3 \times 11$ A1

$1365 = 3 \times 5 \times 7 \times 13$ A1

$1\,{\text{cm}} = 2 \times 2 \times 2 \times 3 \times 5 \times 7 \times 11 \times 13 = 120120$ A1

Note: Only award marks if prime factorisation is used.

[3 marks]

Examiners report

[N/A]

b.i.

[N/A]

b.ii.

[N/A]

Prove that a graph containing a triangle cannot be bipartite.

[3]

Prove that the number of edges in a bipartite graph with n vertices is less than or equal to $\frac{{{n^2}}}{4}$.

[5]

Markscheme

At least two of the three vertices in the triangle must lie on one of the two disjoint sets M1R1

These two are joined by an edge so the graph cannot be bipartite R1

[3 marks]

If there are x vertices in one of the two disjoint sets then there are (n – x) vertices in the other disjoint set M1

The greatest number of edges occurs when all vertices in one set are joined to all vertices in the other to give x(n – x) edges A1

Function f(x) = x(n – x) has a parabolic graph. M1

This graph has a unique maximum at $\left( {\frac{n}{2},\frac{{{n^2}}}{4}} \right)$. A1

so $x(n - x) \leqslant \frac{{{n^2}}}{4}$ R1

[5 marks]

Examiners report

Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.

The positive integer N is expressed in base p as ${({a_n}{a_{n - 1}}…{a_1}{a_0})_p}$ .

Show that when p = 2 , N is even if and only if its least significant digit, ${a_0}$ , is 0.

[5]

Show that when p = 3 , N is even if and only if the sum of its digits is even.

[6]

Markscheme

$N = {a_n} \times {2^n} + {a_{n - 1}} \times {2^{n - 1}} + ... + {a_1} \times 2 + {a_0}$ M1

If ${a_0} = 0$ , then N is even because all the terms are even. R1

Now consider

${a_0} = N - \sum\limits_{r = 1}^n {{a_r} \times {2^r}} $ M1

If N is even, then ${a_0}$ is the difference of two even numbers and is therefore even. R1

It must be zero since that is the only even digit in binary arithmetic. R1

[5 marks]

$N = {a_n} \times {3^n} + {a_{n - 1}} \times {3^{n - 1}} + ... + {a_1} \times 3 + {a_0}$

$ = {a_n} \times ({3^n} - 1) + {a_{n - 1}} \times ({3^{n - 1}} - 1) + ... + {a_1} \times (3 - 1) + {a_n} + {a_{n - 1}} + ... + {a_1} + {a_0}$ M1A1

Since ${3^n}$ is odd for all $n \in {\mathbb{Z}^ + }$ , it follows that ${3^n} - 1$ is even. R1

Therefore if the sum of the digits is even, N is the sum of even numbers and is even. R1

Now consider

${a_n} + {a_{n - 1}} + ... + {a_1} + {a_0} = N - \sum\limits_{r = 1}^n {{a_r}({3^r} - 1)} $ M1

If N is even, then the sum of the digits is the difference of even numbers and is therefore even. R1

[6 marks]

Examiners report

The response to this question was disappointing. Many candidates were successful in showing the ‘if’ parts of (a) and (b) but failed even to realise that they had to continue to prove the ‘only if’ parts.

Given a sequence of non negative integers $\{ {a_r}\} $ show that

(i) $\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} } $ where $x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \} $.

(ii) $\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} } $.

[5]

Hence determine whether the base $3$ number $22010112200201$ is divisible by $8$.

[5]

Markscheme

(i) $(x + 1)(\bmod x) \equiv 1(\bmod x)$ (M1)

${(x + 1)^r}(\bmod x)\left( { \equiv {1^r}(\bmod x)} \right) = 1(\bmod x)$ A1

$\sum\limits_{r - 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) \equiv \sum\limits_{r = 0}^n {{a_r}(\bmod x)} } $ AG

(ii) METHOD 1

$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){3^{2r}}} } $ M1

$ = \sum\limits_{r = 0}^n {({3^{2r + 1}}{a_{2r + 1}} + {3^{2r}}{a_{2r}})} $ M1A1

$ = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} $ AG

METHOD 2

$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = 3{a_1} + {a_0} + 9(3{a_3} + {a_2}) + \ldots + {9^n}(3{a_{2n + 1}} + {a_{2n}})} $ A1

$ = {a_0} + 3{a_1} + {3^2}{a_2} + {3^3}{a_3} + \ldots + {3^{2n + 1}}{a_{2n + 1}}$ M1A1

$ = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} $ AG

[5 marks]

METHOD 1

using part (a) (ii) to separate the number into pairs of digits (M1)

$22010112200201{\text{ }}({\text{base }}3) \equiv 8115621{\text{ }}({\text{base }}9)$ A1

using the sum of digits identity from part (a) (i) (M1)

Note: Award M1 if result from a(i) is used to show that the number is divisible by $2$, even if no other valid working given.

${\text{sum}} = 24$ A1

which is divisible by $8$ A1

hence $22010112200201$ (base $3$) is divisible by $8$

METHOD 2

$\sum\limits_{r = 0}^{13} {{a_r}{3^r}\sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}}){9^r}} } $ (M1)

$ \equiv \sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}})(\bmod 8)} $ A1

$ = {a_0} + 3{a_1} + {a_2} + 3{a_3} + \ldots + {a_{12}} + 3{a_{13}}(\bmod 8)$ M1

$ = (1 + 3 \times 0 + 2 + 3 \times 0 + \ldots + 3 \times 2)(\bmod 8) \equiv 24(\bmod 8)$ A1

$ \equiv 0$ OR divisible by $8$ A1

hence $22010112200201$ (base $3$) is divisible by $8$

[5 marks]

Total [10 marks]

Examiners report

[N/A]

Consider the linear congruence $ax \equiv b\left( {{\text{mod}}\,p} \right)$ where $a,\,b,\,p,\,x \in {\mathbb{Z}^ + }$, $p$ is prime and $a$ is not a multiple of $p$.

State Fermat’s little theorem.

[2]

Use Fermat’s little theorem to show that $x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)$.

[3]

b.i.

Hence solve the linear congruence $5x \equiv 7\left( {{\text{mod}}\,13} \right)$.

[3]

b.ii.

Markscheme

EITHER

if $p$ is prime (and $a$ is any integer) then ${a^p} \equiv a\left( {{\text{mod}}\,p} \right)$ A1A1

Note: Award A1 for $p$ prime and A1 for the congruence or for stating that $p\left| {{a^p} - a} \right.$.

A1A1

Note: Award A1 for $p$ prime and A1 for the congruence or for stating that $p\left| {{a^{p - 1}} - 1} \right.$.

Note: Condone use of equals sign provided $\left( {{\text{mod}}\,p} \right)$ is seen.

[2 marks]

multiplying both sides of the linear congruence by ${a^{p - 2}}$ (M1)

${a^{p - 1}}x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)$ A1

as ${a^{p - 1}} \equiv 1\left( {{\text{mod}}\,p} \right)$ R1

$x \equiv {a^{p - 2}}b\left( {{\text{mod}}\,p} \right)$ AG

[3 marks]

b.i.

$x \equiv {5^{11}} \times 7\left( {{\text{mod}}\,13} \right)$ (M1)

$ \equiv 341796875\left( {{\text{mod}}\,13} \right)$ (A1)

Note: Accept equivalent calculation eg, using ${5^2} \equiv - 1\,{\text{mod}}\,13$.

$ \equiv 4\left( {{\text{mod}}\,13} \right)$ A1

[3 marks]

b.ii.

Examiners report

[N/A]

b.i.

[N/A]

b.ii.

The following diagram shows the graph $G$.

Show that $G$ is bipartite.

[2]

State which two vertices should be joined to make $G$ equivalent to ${K_{3,{\text{ }}3}}$.

[1]

In a planar graph the degree of a face is defined as the number of edges adjacent to that face.

(i) Write down the degree of each of the four faces of $G$.

(ii) Explain why the sum of the degrees of all the faces is twice the number of edges.

[2]

$H$ is a simple connected planar bipartite graph with $e$ edges, $f$ faces, $v$ vertices and $v \ge 3$.

Explain why there can be no face in $H$ of degree

(i) one;

(ii) two;

(iii) three.

[3]

Hence prove that for $H$

(i) $e \ge 2f$;

(ii) $e \le 2v - 4$.

[3]

Hence prove that ${K_{3,{\text{ }}3}}$ is not planar.

[2]

Markscheme

shading alternate vertices or attempting to list pairs M1

EITHER

$ADE$ and $BCF$ A1

as no two equal shadings are adjacent, the graph is bipartite AG

[2 marks]

$C$ and $E$ A1

[1 mark]

(i) degree of each of the four faces is $4$ A1

(ii) each edge bounds two faces R1

[2 marks]

(i) simple so no loops R1

(ii) simple so no multiple edges (and $v > 2$) R1

(iii) bipartite graph so no triangles R1

[3 marks]

(i) $2e = \sum {\deg (f) \ge 4f} $ R1

$e \ge 2f$ AG

(ii) if $H$ is a simple connected planar graph then $e + 2 = v + f$ M1

$e + 2 - v \le \frac{1}{2}e$ M1

$2e + 4 - 2v \le e$

$e \le 2v - 4$ AG

[3 marks]

for ${K_{3,{\text{ }}3}}{\text{ }}v = 6$, and $e = 9$ A1

$9 \le 2 \times 6 - 4$ is not true, therefore ${K_{3,{\text{ }}3}}$ cannot be planar R1AG

[2 marks]

Total [13 marks]

Examiners report

[N/A]

Use the Euclidean algorithm to express gcd (123, 2347) in the form 123p + 2347q, where $p,{\text{ }}q \in \mathbb{Z}$.

[8]

Find the least positive solution of $123x \equiv 1(\bmod 2347)$ .

[3]

Find the general solution of $123z \equiv 5(\bmod 2347)$ .

[3]

State the solution set of $123y \equiv 1(\bmod 2346)$ .

[1]

Markscheme

$2347 = 19 \times 123 + 10$ M1A1

$(123 = 12 \times 10 + 3)$

$10 = 3 \times 3 + 1$ A1

$1(\gcd ) = 10 - 3 \times 3 = 10 - 3 \times (123 - 12 \times 10)$ M1A1

$ = 37 \times 10 - 3 \times 123$ A1

$ = 37 \times (2347 - 19 \times 123) - 3 \times 123$ (for continuation) M1

$ = 37 \times 2347 - 706 \times 123$ A1

[8 marks]

EITHER

$1(\bmod 2347) = ( - 706 \times 123)(\bmod 2347)$ M1A1

$x = - 706 + 2347n$ M1A1

solution: 1641 A1

[3 marks]

$5(\bmod 2347) = ( - 3530 \times 123)(\bmod 2347)$ (M1)

${\text{GS}}:z = - 3530 + k2347$ A1A1

Note: Other common possibilities include $1164 + k2347$ and $8205 + k2347$ .

[3 marks]

empty set (123 and 2346 both divisible by 3) A1

[1 mark]

Examiners report

The majority of candidates were successful in parts (a) and (b). In part (c), some candidates failed to understand the distinction between a particular solution and a general solution. Part (d) was a 1 mark question that defeated all but the few who noticed that the gcd of the numbers concerned was 3.

The planar graph G and its complement $G'$ are both simple and connected.

Given that G has 6 vertices and 10 edges, show that $G'$ is a tree.

Markscheme

the complete graph with 6 vertices has 15 edges so $G'$ has

6 vertices and 5 edges M1A1

the number of faces in $G'$ , $f = 2 + e - v = 1$ M1A1

it is therefore a tree because $f = 1$ R1

Note: Accept it is a tree because $v = e + 1$

[5 marks]

Examiners report

Part (a) was well answered by many candidates.

The graph ${K_{2,{\text{ }}2}}$ is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.

Draw ${K_{2,{\text{ }}2}}$ as a planar graph.

[2]

Draw a spanning tree for ${K_{2,{\text{ }}2}}$.

[1]

Draw the graph of the complement of ${K_{2,{\text{ }}2}}$.

[1]

Show that the complement of any complete bipartite graph does not possess a spanning tree.

[3]

Markscheme

A1A1

Note: Award A1 for a correct version of ${K_{2,{\text{ }}2}}$ and A1 for a correct planar representation.

[2 marks]

[1 mark]

the complete bipartite graph ${K_{m,{\text{ }}n}}$ has two subsets of vertices $A$ and $B$, such that each element of $A$ is connected to every element of $B$ A1

in the complement, no element of $A$ is connected to any element of $B$. The complement is not a connected graph A1

by definition a tree is connected R1

hence the complement of any complete bipartite graph does not possess a spanning tree AG

[3 marks]

Total [7 marks]

Examiners report

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for ${K_{2,2}}$. Some candidates, however, produced a correct non-planar representation of ${K_{2,2}}$.

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for ${K_{2,2}}$ and the correct complement of ${K_{2,2}}$.

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of ${K_{m,n}}$ does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.

Throughout this question, ${(abc \ldots )_n}$ denotes the number $abc \ldots $ written with number base $n$. For example ${(359)_n} = 3{n^2} + 5n + 9$.

(i) Given that ${(43)_n} \times {(56)_n} = {(3112)_n}$, show that $3{n^3} - 19{n^2} - 38n - 16 = 0$.

(ii) Hence determine the value of $n$.

[3]

Determine the set of values of $n$ satisfying ${(13)_n} \times {(21)_n} = {(273)_n}$.

[3]

Show that there are no possible values of $n$ satisfying ${(32)_n} \times {(61)_n} = {(1839)_n}$.

[4]

Markscheme

(i) $n$ satisfies the equation $(4n + 3)(5n + 6) = 3{n^3} + {n^2} + n + 2$ M1A1

$3{n^3} - 19{n^2} - 38n - 16 = 0$ (AG)

(ii) $n = 8$ A1

Note: If extra solutions $( - 1,{\text{ }} - 2/3)$ are not rejected (them just not appearing is fine) do not award the final A1.

[3 marks]

$n$ satisfies the equation $(n + 3)(2n + 1) = 2{n^2} + 7n + 3$ A1

this is an identity satisfied by all $n$ (A1)

$n > 7$ or $n \geqslant 8$ A1

[3 marks]

$n$ satisfies the equation $(3n + 2)(6n + 1) = {n^3} + 8{n^2} + 3n + 9$ A1

${n^3} - 10{n^2} - 12n + 7 = 0$ A1

roots are 11.03, 0.434 and –1.46 A1

since there are no integer roots therefore the product is not true in any number base R1AG

Note: Accept an argument by contradiction that considers the equation modulo $n$, with $n > 10$.

[4 marks]

Examiners report

Well answered.

The fact that this gave an identity was managed by most. Then some showed their misunderstanding by saying any real number. Few noticed that the digit 7 means that the base must be greater than 7.

The cubic equation was generally reached but many candidates then forgot what type of number $n$ had to be. To justify that there are no positive integer roots you need to write down what the roots are. There were a couple of really neat solutions that obtained a contradiction by working modulo $n$.

Solve the recurrence relation ${v_n} + 4{v_{n - 1}} + 4{v_{n - 2}} = 0$ where ${v_1} = 0,{\text{ }}{v_2} = 1$.

[6]

Use strong induction to prove that the solution to the recurrence relation ${u_n} - 4{u_{n - 1}} + 4{u_{n - 2}} = 0$ where ${u_1} = 0,{\text{ }}{u_2} = 1$ is given by ${u_n} = {2^{n - 2}}(n - 1)$.

[8]

Find a simplified expression for ${u_n} + {v_n}$ given that,

(i) $n$ is even.

(ii) $n$ is odd.

[3]

Markscheme

the auxiliary equation is ${m^2} + 4m + 4 = 0$ M1

$m = -2$ A1

the general solution is

${v_n} = (A + Bn) \times {( - 2)^n}$ A1

the boundary conditions give

$0 = -{\text{ }}2(A + B)$

$1 = 4(A + 2B)$ M1

the solution is $A = - \frac{1}{4},{\text{ }}B = \frac{1}{4}$ A1A1

so that ${v_n} = \frac{1}{4}(n - 1){( - 2)^n}{\text{ }}\left( {{\text{or }}(n - 1)( - 2{)^{n - 2}}} \right)$

[6 marks]

$n = 1$ gives $(1 - 1) \times \frac{1}{2} = 0$ which is correct A1

$n = 2$ gives $(2 - 1) \times 1 = 1$ which is correct A1

Note: Must be checked for $n = 1$ and 2, other values gain no marks.

assume that the result is true for all positive integers $ \leqslant k$ M1

${u_{k + 1}} = 4{u_k} - 4{u_{k - 1}}$ (M1)

${u_{k + 1}} = 4 \times {2^{k - 2}}(k - 1) - 4 \times {2^{k - 3}}(k - 2)$ A1

$ = {2^{k - 1}}(2k - 2 - k + 2)$ or equivalent A1

$ = k{2^{k - 1}}$ A1

therefore true for $n \leqslant k \Rightarrow $ true for $n = k + 1$ and since true for $n = 1$ and $n = 2$, the result is proved by strong induction R1

Note: Only award the R1 if at least four of the above marks have been awarded.

Note: Allow true for $k$ and $k - 1$ (in 2 places) instead of stronger statement.

Note: First M1 does not have to be given for further marks to be gained but second (M1) does.

[8 marks]

(i) ${u_n} + {v_n} = {2^{n - 2}}(n - 1) + {( - 2)^{n - 2}}(n - 1)$

when $n$ is even ${u_n} + {v_n} = {2^{n - 2}}(n - 1) + {2^{n - 2}}(n - 1)$ M1

$ = {2^{n - 1}}(n - 1)$ A1

(ii) when $n$ is odd ${u_n} + {v_n} = 0$ A1

[3 marks]

Examiners report

This was either done well and completely correct or very little achieved at all (working out ${v_0}$ for some reason). As expected a few candidates forgot what to do for a repeated root. The varied response to this question was surprising since it is just standard book work.

Strong induction proved to be a very good discriminator. Some candidates knew exactly what to do and did it well, others had no idea. Common mistakes were not checking $n = 2$ and 2, trying ordinary induction and worse of all assuming the very thing that they were trying to prove.

Most candidates that had the 2 expressions, knew how to get rid of the minus sign in the 2 cases. Some candidates could not attempt this as they had not completed part (a) although when it was wrong, follow through marks could be obtained.

Use the Euclidean algorithm to show that 1463 and 389 are relatively prime.

[4]

Find positive integers $a$ and $b$ such that \[1463a - 389b = 1\].

[5]

Markscheme

$1463 = 3 \times 389 + 296$ M1A1

$389 = 1 \times 296 + 93$

$296 = 3 \times 93 + 17$ A1

$93 = 5 \times 17 + 8$

$17 = 2 \times 8 + 1$ which shows that the gcd is 1 A1

hence 1463 and 389 are relatively prime AG

[4 marks]

EITHER

$1 = 17 - 2 \times 8$ (M1)

$ = 17 - 2 \times (93 - 5 \times 17) = 11 \times 17 - 2 \times 93$ (A1)

$ = 11 \times (296 - 3 \times 93) - 2 \times 93 = 11 \times 296 - 35 \times 93$ (A1)

$ = 11 \times 296 - 35 \times (389 - 296) = 46 \times 296 - 35 \times 389$

$ = 46 \times (1463 - 3 \times 389) - 35 \times 389$ (A1)

$ = 46 \times 1463 - 173 \times 389$ A1

$(a = 46,{\text{ }}b = 173)$

method of keeping track of the linear combinations from the beginning (could be seen alongside the working in (a))

$(1,{\text{ }}0)$		$(0,{\text{ }}1)$
		$ - 3(1,{\text{ }}0)$
		$( - 3,{\text{ }}1)$

(M1)(A1)

$ - ( - 3,{\text{ }}1)$
$(4,{\text{ }} - 1)$
		$ - 3(4,{\text{ }} - 1)$
		$( - 15,{\text{ }}4)$

(A1)

$ - 5( - 15,{\text{ }}4)$

$(79,{\text{ }} - 21)$ (A1)

		$ - 2(79,{\text{ }} - 21)$
		$( - 173,{\text{ }}46)$

so $ - 173 \times 389 + 46 \times 1463 = 1$ giving $46 \times 1463 - 173 \times 389 = 1$ A1

$(a = 46,{\text{ }}b = 173)$

Note: Accept any positive answers of the form $a = 46 + 389t,{\text{ }}b = 173 + 1463t,{\text{ }}t$ an integer.

[5 marks]

Examiners report

Very well answered. Some candidates lost the final mark by not saying that their working showed that the greatest common divisor (gcd) was 1.

The working backwards method was generally well known but there were arithmetic mistakes. Some candidates did not realise that their aim was to keep 1 as a combination of two remainders. The final answer could have been checked with the calculator as could intermediary steps. What was sadly less well known was the linear combinations format of laying the work out. See the OR method in the mark scheme. This makes the numerical work much less tedious and deserves to be better known.

In the context of graph theory, explain briefly what is meant by a circuit;

[1]

a.i.

In the context of graph theory, explain briefly what is meant by an Eulerian circuit.

[1]

a.ii.

The graph $G$ has six vertices and an Eulerian circuit. Determine whether or not its complement $G'$ can have an Eulerian circuit.

[3]

Find an example of a graph $H$, with five vertices, such that $H$ and its complement $H'$ both have an Eulerian trail but neither has an Eulerian circuit. Draw $H$ and $H'$ as your solution.

[4]

Markscheme

a circuit is a walk that begins and ends at the same vertex and has no repeated edges A1

[1 mark]

a.i.

an Eulerian circuit is a circuit that contains every edge of a graph A1

[1 mark]

a.ii.

if $G$ has an Eulerian circuit all vertices are even (are of degree 2 or 4) A1

hence, $G'$ must have all vertices odd (of degree 1 or 3) R1

hence, $G'$ cannot have an Eulerian circuit R1

Note: Award A1 to candidates who begin by considering a specific $G$ and $G'$ (diagram). Award R1R1 to candidates who then consider a general $G$ and $G'$.

[3 marks]

for example

M17/5/MATHL/HP3/ENG/TZ0/DM/M/03.c

Notes: Each graph must have 3 vertices of order 2 and 2 odd vertices. Award A2 if one of the graphs satisfies that and the final A2 if the other graph is its complement.

[4 marks]

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

When numbers are written in base n, ${33^2} = 1331$.

By writing down an appropriate polynomial equation, determine the value of n.

[4]

Rewrite the above equation with numbers in base 7.

[6]

Markscheme

the equation can be written as

${(3n + 3)^2} = {n^3} + 3{n^2} + 3n + 1$ M1A1

any valid method of solution giving n = 8 (M1)A1

Note: Attempt to change at least one side into an equation in n gains the M1.

[4 marks]

METHOD 1

as decimal numbers,

${(33)_8} = 27,{\text{ }}{(1331)_8} = 729$ A1A1

converting to base 7 numbers,

$27 = {(36)_7}$ A1

7)729 M1
7)104(1
7) 14(6
7) 2(0
7) 0(2

therefore $729 = {(2061)_7}$ A1

the required equation is

${36^2} = 2061$ A1

METHOD 2

as a decimal number, ${(33)_8} = 27$ A1

converting to base 7,

$27 = {(36)_7}$ A1

multiplying base 7 numbers

   36
× 36
1440     M1
321     A1
2061   A1

the required equation is

${36^2} = 2061$ A1

Note: Allow M1 for showing the method of converting a number to base 7 regardless of what number they convert.

[6 marks]

Examiners report

Part (a) was a good indicator of overall ability. Many candidates did not write both sides of the equation in terms of n and thus had an impossible equation, which should have made them realise that they had a mistake. The answers that were given in (a) and (b) could have been checked, so that the candidate knew they had done it correctly.

Part (b) was not well answered and of those candidates that did, some only gave one side of the equation in base 7. The answers that were given in (a) and (b) could have been checked, so that the candidate knew they had done it correctly.

Let $f(n) = {n^5} - n,{\text{ }}n \in {\mathbb{Z}^ + }$.

Find the values of $f(3)$, $f(4)$ and $f(5)$.

[2]

Use the Euclidean algorithm to find

(i) $\gcd \left( {f(3),{\text{ }}f(4)} \right)$;

(ii) $\gcd \left( {f(4),{\text{ }}f(5)} \right)$.

[4]

Explain why $f(n)$ is always exactly divisible by $5$.

[1]

By factorizing $f(n)$ explain why it is always exactly divisible by $6$.

[4]

Determine the values of $n$ for which $f(n)$ is exactly divisible by $60$.

[3]

Markscheme

$240,{\rm{ }}1020,{\rm{ }}3120$ A2

Note: Award A2 for three correct answers, A1 for two correct answers.

[2 marks]

(i) $1020 = 240 \times 4 + 60$ (M1)

$240 = 60 \times 4$

$\gcd (1020,{\text{ }}240) = 60$ A1

(ii) $3120 = 1020 \times 3 + 60$ (M1)

$1020 = 60 \times 17$

$\gcd (1020,{\text{ }}3120) = 60$ A1

Note: Must be done by Euclid’s algorithm.

[4 marks]

by Fermat’s little theorem with $p = 5$ R1

${n^5} \equiv n(\bmod 5)$

so 5 divides $f(n)$

[1 mark]

$f(n) = n({n^2} - 1)({n^2} + 1) = n(n - 1)(n + 1)({n^2} + 1)$ (A1)A1

$n - 1,{\text{ }}n,{\text{ }}n + 1$ are consecutive integers and so contain a multiple of $2$ and $3$ R1R1

Note: Award R1 for justification of $2$ and R1 for justification of $3$.

And therefore $f(n)$ is a multiple of $6$. AG

[4 marks]

from (c) and (d) $f(n)$ is always divisible by $30$ R1

considering the factorization, it is divisible by $60$ when $n$ is an odd number A1

or when $n$ is a multiple of $4$ A1

Note: Accept answers such as when $n$ is not congruent to $2(\bmod 4)$.

[3 marks]

Total [14 marks]

Examiners report

Well answered.

Also well answered. A few candidates did not use the Euclidean algorithm to find the gcd as instructed.

Many candidates essential said it was true because it was! There is only one mark which means one minute, so it must be a short answer which it is by using Fermat’s Little Theorem.

Some good answers but too many did not factorize as instructed, so that they could then spot the consecutive numbers.

Only the better candidates realised that they had to find another factor of $2$.

(i) One version of Fermat’s little theorem states that, under certain conditions,

\[{a^{p - 1}} \equiv 1(\bmod p).\]

Show that this result is not valid when a = 4, p = 9 and state which

condition is not satisfied.

(ii) Given that ${5^{64}} \equiv n(\bmod 7)$, where $0 \leqslant n \leqslant 6$, find the value of n.

[8]

Find the general solution to the simultaneous congruences

\[x \equiv 3(\bmod 4)\]

\[3x \equiv 2(\bmod 5).\]

[6]

Markscheme

(i) ${4^8} = 65536 \equiv 7(\bmod 9)$ A1

not valid because 9 is not a prime number R1

Note: The R1 is independent of the A1.

(ii) using Fermat’s little theorem M1

${5^6} \equiv 1(\bmod 7)$ A1

therefore

${({5^6})^{10}} = {5^{60}} \equiv 1(\bmod 7)$ A1

also, ${5^4} = 625$ M1

$ \equiv 2(\bmod 7)$ A1

therefore

${5^{64}} \equiv 1 \times 2 \equiv 2(\bmod 7)\,\,\,\,\,{\text{(so }}n = 2)$ A1

Note: Accept alternative solutions not using Fermat.

[8 marks]

EITHER

solutions to $x \equiv 3(\bmod 4)$ are

3, 7, 11, 15, 19, 23, 27, … A1

solutions to $3x \equiv 2(\bmod 5).$ are

4, 9, 14, 19 … (M1)A1

so a solution is x =19 A1

using the Chinese remainder theorem (or otherwise) (M1)

the general solution is $x = 19 + 20n{\text{ }}(n \in \mathbb{Z})$ A1

$\left( {{\text{accept }}19(\bmod 20)} \right)$

$x = 3 + 4t \Rightarrow 9 + 12t \equiv 2(\bmod 5)$ M1A1

$ \Rightarrow 2t \equiv 3(\bmod 5)$ A1

$ \Rightarrow 6t \equiv 9(\bmod 5)$

$ \Rightarrow t \equiv 4(\bmod 5)$ A1

so $t = 4 + 5n{\text{ and }}x = 19 + 20n{\text{ }}(n \in \mathbb{Z})$ M1A1

$\left( {{\text{accept }}19(\bmod 20)} \right)$

Note: Also accept solutions done by formula.

[6 marks]

Examiners report

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg ${5^4} \equiv 2,{\text{ }}{5^8} \equiv 4$ and ${5^3}\equiv- 1(\bmod 7)$ were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to $3(\bmod 4)$and $4(\bmod 5)$ and the use of an appropriate formula.

Part (a) was generally well answered with a variety of methods seen in (a)(ii). This was set with Fermat’s Little Theorem in mind but in the event many candidates started off with many different powers of 5, eg ${5^4} \equiv 2,{\text{ }}{5^8} \equiv 4$ and ${5^3}\equiv - 1(\bmod 7)$ were all seen. A variety of methods was also seen in (b), ranging from use of the Chinese Remainder Theorem, finding tables of numbers congruent to $3(\bmod 4)$and $4(\bmod 5)$ and the use of an appropriate formula.

(a) (i) Write down the general solution of the recurrence relation ${u_n} + 2{u_{n - 1}} = 0,{\text{ }}n \geqslant 1$.

(ii) Find a particular solution of the recurrence relation ${u_n} + 2{u_{n - 1}} = 3n - 2,{\text{ }}n \geqslant 1$, in the

form ${u_n} = An + B$, where $A,{\text{ }}B \in \mathbb{Z}$.

(iii) Hence, find the solution to ${u_n} + 2{u_{n - 1}} = 3n - 2,{\text{ }}n \geqslant 1$ where ${u_1} = 7$.

(b) Find the solution of the recurrence relation ${u_n} = 2{u_{n - 1}} - 2{u_{n - 2}},{\text{ }}n \geqslant 2$, where ${u_0} = 2,{\text{ }}{u_1} = 2$. Express your solution in the form ${2^{f(n)}}\cos \left( {g(n)\pi } \right)$, where the functions f and g map $\mathbb{N}$ to $\mathbb{R}$.

Markscheme

(a) (i) use of auxiliary equation or recognition of a geometric sequence (M1)

${u_n} = {( - 2)^n}{u_0}$ or $ = {\text{A}}{( - 2)^n}$ or ${u_1}{( - 2)^{n - 1}}$ A1

(ii) substitute suggested solution M1

$An + B + 2\left( {A(n - 1) + B} \right) = 3n - 2$ A1

equate coefficients of powers of n and attempt to solve (M1)

$A = 1,{\text{ }}B = 0$ A1

(so particular solution is ${u_n} = n$)

(iii) use of general solution = particular solution + homogeneous solution (M1)

${u_n} = {\text{C}}{( - 2)^2} + n$ A1

attempt to find C using ${u_1} = 7$ M1

${u_n} = - 3{( - 2)^n} + n$ A1

[10 marks]

(b) the auxiliary equation is ${r^2} - 2r + 2 = 0$ A1

solutions: ${r_1},{\text{ }}{r_2} = 1 \pm {\text{i}}$ A1

general solution of the recurrence: ${u_n} = {\text{A}}{(1 + {\text{i}})^n} + {\text{B}}{(1 - {\text{i}})^n}$ or trig form A1

attempt to impose initial conditions M1

$A = B = 1$ or corresponding constants for trig form A1

${u_n} = {2^{\left( {\frac{n}{2} + 1} \right)}} \times \cos \left( {\frac{{n\pi }}{4}} \right)$ A1A1

[7 marks]

Total [17 marks]

Examiners report

[N/A]

A version of Fermat’s little theorem states that when p is prime, a is a positive integer and a and p are relatively prime, then ${a^{p - 1}} \equiv 1(\bmod p)$.

Use the above result to show that if p is prime then ${a^p} \equiv a(\bmod p)$ where a is any positive integer.

[4]

Show that ${2^{341}} \equiv 2(\bmod 341)$.

[7]

(i) State the converse of the result in part (a).

(ii) Show that this converse is not true.

[2]

Markscheme

consider two cases M1

let a and p be coprime

${a^{p - 1}} \equiv 1(\bmod p)$ R1

$ \Rightarrow {a^p} \equiv a(\bmod p)$

let a and p not be coprime

$a \equiv 0(\bmod p)$ M1

${a^p} = 0(\bmod p)$ R1

$ \Rightarrow {a^p} = a(\bmod p)$

so ${a^p} = a(\bmod p)$ in both cases AG

[4 marks]

$341 = 11 \times 31$ (M1)

we know by Fermat’s little theorem

${2^{10}} \equiv 1(\bmod 11)$ M1

$ \Rightarrow {2^{341}} \equiv {({2^{10}})^{34}} \times 2 \equiv {1^{34}} \times 2 \equiv 2(\bmod 11)$ A1

also ${2^{30}} \equiv 1(\bmod 31)$ M1

$ \Rightarrow {2^{341}} \equiv {({2^{30}})^{11}} \times {2^{11}}$ A1

$ \equiv {1^{11}} \times 2048 \equiv 2(\bmod 31)$ A1

since 31 and 11 are coprime R1

${2^{341}} \equiv 2(\bmod 341)$ AG

[7 marks]

(i) converse: if ${a^p} = a(\bmod p)$ then p is a prime A1

(ii) from part (b) we know ${2^{341}} \equiv 2(\bmod 341)$

however, 341 is composite

hence 341 is a counter-example and the converse is not true R1

[2 marks]

Examiners report

There were very few fully correct answers. In (b) the majority of candidates assumed that 341 is a prime number and in (c) only a handful of candidates were able to state the converse.

The weighted graph K, representing the travelling costs between five customers, has the following adjacency table.

Draw the graph $K$.

[2]

Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to the travelling salesman problem for K.

[4]

By removing customer A, use the method of vertex deletion, to determine a lower bound to the travelling salesman problem for K.

[4]

Markscheme

complete graph on five vertices A1

weights correctly marked on graph A1

[2 marks]

clear indication that the nearest-neighbour algorithm has been applied M1

DA (or 7) A1

AB (or 1) BC (or 9) A1

CE (or 3), ED (or 12), giving UB = 32 A1

[4 marks]

attempt to use the vertex deletion method M1

minimum spanning tree is ECBD A1

(EC 3, BD 8, BC 9 total 20)

reconnect A with the two edges of least weight, namely AB (1) and AE (4) M1

lower bound is 25 A1

[4 marks]

Examiners report

[N/A]

(i) Given that $a \equiv d(\bmod n)$ and $b \equiv c(\bmod n)$ prove that

\[(a + b) \equiv (c + d)(\bmod n){\text{ .}}\]

(ii) Hence solve the system

\[\left\{ {\begin{array}{*{20}{r}}
{2x + 5y \equiv 1(\bmod 6)} \\
{x + y \equiv 5(\bmod 6)}
\end{array}} \right.\]

[11]

Show that ${x^{97}} - x + 1 \equiv 0(\bmod 97)$ has no solution.

[3]

Markscheme

(i) $a \equiv d(\bmod n){\text{ and }}b \equiv c(\bmod n)$

so $a - d = pn{\text{ and }}b - c = qn$ , M1A1

$a - d + b - c = pn + qn$

$(a + b) - (c + d) = n(p + q)$ A1

$(a + b) \equiv (c + d)(\bmod n)$ AG

(ii) $\left\{ {\begin{array}{*{20}{r}}
{2x + 5y \equiv 1(\bmod 6)} \\
{x + y \equiv 5(\bmod 6)}
\end{array}} \right.$

adding $3x + 6y \equiv 0(\bmod 6)$ M1

$6y \equiv 0(\bmod 6){\text{ so }}3x \equiv 0(\bmod 6)$ R1

$x \equiv 0{\text{ or }}x \equiv 2{\text{ or }}x \equiv 4(\bmod 6)$ A1A1A1

for $x \equiv 0,{\text{ }}0 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 5(\bmod 6)$ A1

for $x \equiv 2,{\text{ }}2 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 3(\bmod 6)$ A1

If $x \equiv 4(\bmod 6),{\text{ }}4 + y \equiv 5(\bmod 6){\text{ so }}y \equiv 1(\bmod 6)$ A1

[11 marks]

Suppose x is a solution

97 is prime so ${x^{97}} \equiv x(\bmod 97)$ M1

${x^{97}} - x \equiv 0(\bmod 97)$ A1

${x^{97}} - x + 1 \equiv 1 \ne 0(\bmod 97)$

Hence there are no solutions R1

[3 marks]

Examiners report

Part (a) (i) was not found difficult but using it in part (a)(ii) resulted in two or three correct lines and then abandonment of the problem.

The sequence $\{ {u_n}\} ,{\text{ }}n \in \mathbb{N}$, satisfies the recurrence relation ${u_{n + 1}} = 7{u_n} - 6$.

Given that ${u_0} = 5$, find an expression for ${u_n}$ in terms of $n$.

[5]

The sequence $\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}$, satisfies the recurrence relation ${v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}$.

Given that ${v_0} = 4$ and ${v_1} = 44$, find an expression for ${v_n}$ in terms of $n$.

[7]

The sequence $\{ {v_n}\} ,{\text{ }}n \in \mathbb{N}$, satisfies the recurrence relation ${v_{n + 2}} = 10{v_{n + 1}} + 11{v_n}$.

Show that ${v_n} - {u_n} \equiv 15(\bmod 16),{\text{ }}n \in \mathbb{N}$.

[4]

Markscheme

METHOD 1

attempting to find a solution in the form ${u_n} = A{7^n} + B$ M1

EITHER

eg, and ${u_0} = 5 \Rightarrow 5 = A + B{\text{ and }}{u_1} = 29 \Rightarrow 29 = 7A + B$ A1

$A{7^{n + 1}} + B = A{7^{n + 1}} + 7B - 6\;\;\;$(or equivalent) A1

THEN

attempting to solve for $A$ and $B$ (M1)

${u_n} = 4 \times {7^n} + 1$ A1A1

Note: Accept $A = 4,{\text{ }}B = 1$ provided the first M1 is awarded.

METHOD 2

attempting an iterative method eg, ${u_1} = 7{\text{(}}5) - 6$ and

${u_2} = {7^2}{\text{(}}5) - 6{\text{(}}7 + 1){\text{ }}(etc)$ (M1)

${u_n} = 5 \times {7^n} - 6\left( {\frac{{{7^n} - 1}}{{7 - 1}}} \right)$ M1A1

Note: Award M1 for attempting to express ${u_n}$ in terms of $n$.

${u_n} = 4 \times {7^n} + 1$ A1A1

METHOD 3

attempting to find a solution in the form ${u_n} = A{7^n} + B$ M1

$A(n + 1) + B = 7(An + B) - 6$

$7B - 6 = B$ A1

attempting to solve for $A$ (M1)

${u_n} = 4 \times {7^n} + 1$ A1A1

METHOD 4

${u_{n + 1}} - 7{u_n} + 6 - ({u_n} - 7{u_{n + 1}} + 6) = 0 \Rightarrow {u_{n + 1}} - 8{u_n} + 7{u_{n - 1}} = 0$

${r^2} - 8r + 7 = 0$

$r = 1,{\text{ }}7$

attempting to find a solution in the form ${u_n} = A{7^n} + B$ M1

EITHER

eg, ${u_0} = 5 \Rightarrow 5 = A + B{\text{ and }}{u_1} = 29 \Rightarrow 29 = 7A + B$ A1

$A{7^{n + 1}} + B = A{7^{n + 1}} + 7B - 6\;\;\;$(or equivalent) A1

THEN

attempting to solve for $A$ and $B$ (M1)

${u_n} = 4 \times {7^n} + 1$ A1A1

[5 marks]

attempting to find the auxiliary equation M1

${r^2} - 10r - 11 = 0\;\;\;\left( {(r - 11)(r + 1) = 0} \right)$ A1

$r = 11,{\text{ }}r = - 1$ A1

${v_n} = A{11^n} + B{( - 1)^n}$ (M1)

attempting to use the initial conditions M1

$A + B = 4,{\text{ }}11A - B = 44$ A1

${v_n} = 4 \times {11^n}$ A1

[7 marks]

${v_n} - {u_n} = 4({11^n} - {7^n}) - 1$ M1

EITHER

$ = 4(11 - 7)({11^{n - 1}} + \ldots + {7^{n - 1}}) - 1$ M1A1

$ = 4\left( {{{(7 + 4)}^n} - {7^n}} \right) - 1$ A1

subtracting the ${7^n}$ from the expanded first bracket M1

THEN

obtaining $16$ times a whole number $ - 1$ A1

${v_n} - {u_n} \equiv 15(\bmod 16),{\text{ }}n \in \mathbb{N}$ AG

[4 marks]

Total [16 marks]

Examiners report

In part (a), a good number of candidates were able to ‘see’ the solution form for ${u_n}$ and then (often in non-standard ways) successfully obtain ${u_n} = 4 \times {7^n} + 1$. A variety of methods and interesting approaches were seen here including use of the general closed form solution, iteration, substitution of ${u_n} = 4 \times {7^n} + 1$, substitution of ${u_n} = An + B$ and, interestingly, conversion to a second-degree linear recurrence relation. A number of candidates erroneously converted the recurrence relation to a quadratic auxiliary equation and obtained ${u_n} = {c_1}{(6)^n} + {c_2}{(1)^n}$.

Compared to similar recurrence relation questions set in recent examination papers, part (b) was reasonably well attempted with a substantial number of candidates correctly obtaining ${v_n} = 4{(11)^n}$. It was pleasing to note the number of candidates who could set up the correct auxiliary equation and use the two given terms to obtain the required solution. It appeared that candidates were better prepared for solving second-order linear recurrence relations compared to first-order linear recurrence relations.

Most candidates found part (c) challenging. Only a small number of candidates attempted to either factorise ${11^n} - {2^n}$ or to subtract ${7^n}$ from the expansion of ${(7 + 4)^n}$. It was also surprising how few went for the option of stating that 11 and 7 are congruent $\bmod 4$ so ${11^n} - {7^n} \equiv (\bmod 4)$ and hence is a multiple of 4.

The diagram shows a weighted graph with vertices A, B, C, D, E, F, G. The weight of each edge is marked on the diagram.

(i) Explain briefly why the graph contains an Eulerian trail but not an Eulerian circuit.

(ii) Write down an Eulerian trail.

[4]

(i) Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D.

(ii) State the minimum total weight.

[8]

Markscheme

(i) there is an Eulerian trail because there are only 2 vertices of odd degree R1

there is no Eulerian circuit because not all vertices have even degree R1

(ii) eg GBAGFBCFECDE A2

[4 marks]

(i)

$\begin{array}{*{20}{l}}
{{\text{Step}}}&{{\text{Vertices labelled}}}&{{\text{Working values}}}&{} \\
1&{\text{A}}&{{\text{A(0), B-3, G-2}}}&{{\boldsymbol{M1A1}}} \\
2&{{\text{A, G}}}&{{\text{A(0), G(2), B-3, F-8}}}&{{\boldsymbol{A1}}} \\
3&{{\text{A, G, B}}}&{{\text{A(0), G(2), B(3), F-7, C-10}}}&{{\boldsymbol{A1}}} \\
4&{{\text{A, G, B, F}}}&{{\text{A(0), G(2), B(3), F(7), C-9, E-12}}}&{} \\
5&{{\text{A, G, B, F, C}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E-10, D-15}}}&{{\boldsymbol{A1}}} \\
6&{{\text{A, G, B, F, C, E}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D-14}}}&{} \\
7&{{\text{A, G, B, F, C, E, D}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D(14)}}}&{{\boldsymbol{A1}}}
\end{array}$

Note: In both (i) and (ii) accept the tabular method including back tracking or labels by the vertices on a graph.

Note: Award M1A1A1A1A0A0 if final labels are correct but intermediate ones are not shown.

(ii) minimum weight path is ABFCED A1

minimum weight is 14 A1

Note: Award the final two A1 marks whether or not Dijkstra’s Algorithm is used.

[8 marks]

Examiners report

In part (a) the criteria for Eulerian circuits and trails were generally well known and most candidates realised that they must start/finish at G/E. Candidates who could not do (a) generally struggled on the paper.

For part (b) the layout varied greatly from candidate to candidate. Not all candidates made their method clear and some did not show the temporary labels. It is recommended that teachers look at the tabular method with its backtracking system as it is an efficient way of tackling this type of problem and has a very clear layout.

(a) Use the Euclidean algorithm to find gcd($12\,306$, 2976) .

(b) Hence give the general solution to the diophantine equation $12\,306$x + 2976y = 996 .

Markscheme

(a) $12\,306 = 4 \times 2976 + 402$ M1

$2976 = 7 \times 402 + 162$ M1

$402 = 2 \times 162 + 78$ A1

$162 = 2 \times 78 + 6$ A1

$78 = 13 \times 6$

therefore gcd is 6 R1

[5 marks]

(b) $6|996$ means there is a solution

$6 = 162 - 2(78)$ (M1)(A1)

$ = 162 - 2\left( {402 - 2(162)} \right)$

$ = 5(162) - 2(402)$ (A1)

$ = 5(2976) - 7(402)} \right) - 2(402)$

$ = 5(2976) - 37(402)$ (A1)

$ = 5(2976) - 37\left( {12\,306 - 4(2976)} \right)$

$ = 153(2976) - 37(12\,306)$ (A1)

$996 = 25\,398(2976) - 6142(12\,306)$

$ \Rightarrow {x_0} = - 6142,{\text{ }}{y_0} = 25\,398$ (A1)

$ \Rightarrow x = - 6142 + \left( {\frac{{2976}}{6}} \right)t = - 6142 + 496t$

$ \Rightarrow y = 25\,398 - \left( {\frac{{12\,306}}{6}} \right)t = 25\,398 - 2051t$ M1A1A1

[9 marks]

Total [14 marks]

Examiners report

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. Most candidates were able to start part (b), but a number made errors on the way and quite a number failed to give the general solution.

Use the Euclidean algorithm to find the greatest common divisor of the numbers 56 and 315.

[4]

(i) Find the general solution to the diophantine equation $56x + 315y = 21$.

(ii) Hence or otherwise find the smallest positive solution to the congruence $315x \equiv 21$ (modulo 56) .

[9]

Markscheme

$315 = 5 \times 56 + 35$ M1

$56 = 1 \times 35 + 21$

$35 = 1 \times 21 + 14$ A1

$21 = 1 \times 14 + 7$

$14 = 2 \times 7$ A1

therefore gcd = 7 A1

[4 marks]

(i) $7 = 21 - 14$ M1

$ = 21 - (35 - 21)$

$ = 2 \times 21 - 35$ (A1)

$ = 2 \times (56 - 35) - 35$

$ = 2 \times 56 - 3 \times 35$ (A1)

$ = 2 \times 56 - 3 \times (315 - 5 \times 56)$

$ = 17 \times 56 - 3 \times 315$ (A1)

therefore $56 \times 51 + 315 \times (- 9) = 21$ M1

$x = 51,{\text{ }}y = - 9$ is a solution (A1)

the general solution is $x = 51 + 45N$ , $y = - 9 - 8N$ , $N \in \mathbb{Z}$ A1A1

(ii) putting N = –2 gives y = 7 which is the required value of x A1

[9 marks]

Examiners report

This question was generally well answered although some candidates were unable to proceed from a particular solution of the Diophantine equation to the general solution.

Given that a , $b \in \mathbb{N}$ and $c \in {\mathbb{Z}^ + }$, show that if $a \equiv 1(\bmod c)$ , then $ab \equiv b(\bmod c)$ .

[2]

Using mathematical induction, show that ${9^n} \equiv 1(\bmod 4)$ , for $n \in \mathbb{N}$ .

[6]

The positive integer M is expressed in base 9. Show that M is divisible by 4 if the sum of its digits is divisible by 4.

[4]

Markscheme

$a = \lambda c + 1$ M1

so $ab = \lambda bc + b \Rightarrow ab \equiv b(\bmod c)$ A1AG

[2 marks]

the result is true for n = 0 since ${9^0} = 1 \equiv 1(\bmod 4)$ A1

assume the result is true for n = k , i.e. ${9^k} \equiv 1(\bmod 4)$ M1

consider ${9^{k + 1}} = 9 \times {9^k}$ M1

$ \equiv 9 \times 1(\bmod 4)$ or $1 \times {9^k}(\bmod 4)$ A1

$ \equiv 1(\bmod 4)$ A1

so true for $n = k \Rightarrow $ true for n = k + 1 and since true for n = 0 result follows by induction R1

Note: Do not award the final R1 unless both M1 marks have been awarded.

Note: Award the final R1 if candidates state n = 1 rather than n = 0

[6 marks]

let $M = {({a_n}{a_{n - 1}}…{a_0})_9}$ (M1)

$ = {a_n} \times {9^n} + {a_{n - 1}} \times {9^{n - 1}} + ... + {a_0} \times {9^0}$ A1

EITHER

$ \equiv {a_n}(\bmod 4) + {a_{n - 1}}(\bmod 4) + ... + {a_0}(\bmod 4)$ A1

$ \equiv \sum {{a_i}(\bmod 4)} $ A1

so M is divisible by 4 if $\sum {{a_i}} $ is divisible by 4 AG

$ = {a_n}({9^n} - 1) + {a_{n - 1}}({9^{n - 1}} - 1) + ... + {a_1}({9^1} - 1)$

$ + {a_n} + {a_{n - 1}} + ... + {a_1} + {a_0}$ A1

Since ${9^n} \equiv 1(\bmod 4)$ , it follows that ${9^n} - 1$ is divisible by 4, R1

so M is divisible by 4 if $\sum {{a_i}} $ is divisible by 4 AG

[4 marks]

Examiners report

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

Two mathematicians are planning their wedding celebration and are trying to arrange the seating plan for the guests. The only restriction is that all tables must seat the same number of guests and each table must have more than one guest. There are fewer than 350 guests, but they have forgotten the exact number. However they remember that when they try to seat them with two at each table there is one guest left over. The same happens with tables of 3, 4, 5 and 6 guests. When there were 7 guests per table there were none left over. Find the number of guests.

Markscheme

let x be the number of guests

$x \equiv 1(\bmod 2)$

$x \equiv 1(\bmod 3)$

$x \equiv 1(\bmod 4)$

$x \equiv 1(\bmod 5)$

$x \equiv 1(\bmod 6)$

$x \equiv 0(\bmod 7)$ congruence (i) (M1)(A2)

the equivalent of the first five lines is

$x \equiv 1\left( {\bmod ({\text{lcm of 2, 3, 4, 5, 6}})} \right) \equiv 1(\bmod 60)$ A1

$ \Rightarrow x = 60t + 1$

from congruence (i) $60t + 1 \equiv 0(\bmod 7)$ M1A1

$60t \equiv - 1(\bmod 7)$

$60t \equiv 6(\bmod 7)$

$4t \equiv 6(\bmod 7)$

$2t \equiv 3(\bmod 7)$ A1

$ \Rightarrow t = 7u + 5\,\,\,\,\,{\text{(or equivalent)}}$ A1

hence $x = 420u + 300 + 1$ A1

$ \Rightarrow x = 420u + 301$

smallest number of guests is 301 A1 N6

Note: Accept alternative correct solutions including exhaustion or formula from Chinese remainder theorem.

[10 marks]

Examiners report

There were a number of totally correct solutions to this question, but many students were unable to fully justify the result. Some candidates had learnt a formula to apply to the Chinese remainder theorem, but could not apply it well in this situation. Many worked with the conditions for divisibility but did not make much progress with the justification.

Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.

[7]

The representation of the positive integer N in base p is denoted by ${(N)_p}$ .

If ${({5^{{{(126)}_7}}})_7} = {({a_n}{a_{n - 1}} \ldots {a_1}{a_0})_7}$ , find ${a_0}$ .

[9]

Markscheme

consider the decimal number $A = {a_n}{a_{n - 1}} \ldots {a_0}$ M1

$A = {A_n} \times {10^n} + {a_{n - 1}} \times {10^{n - 1}} + \ldots + {a_1} \times 10 + {a_0}$ M1

$ = {a_n} \times ({10^n} - 1) + {a_{n - 1}} \times ({10^{n - 1}} - 1) + \ldots + {a_1} \times (10 - 1) + {a_n} + {a_{n - 1}} + \ldots + {a_0}$ M1A1

$ = {a_n} \times 99 \ldots 9(n{\text{ digits}}) + {a_{n - 1}} \times 99 \ldots 9(n - 1{\text{ digits}}) + \ldots + 9{a_1} + {a_n} + {a_{n - 1}} + \ldots + {a_0}$ A1

all the numbers of the form 99…9 are divisible by 9 (to give 11…1), R1

hence A is divisible by 9 if $\sum\limits_{i = 0}^n {{a_i}} $ is divisible by 9 R1

Note: A method that uses the fact that ${10^t} \equiv 1(\bmod 9)$ is equally valid.

[7 marks]

by Fermat’s Little Theorem ${5^6} \equiv 1(\bmod 7)$ M1A1

${(126)_7} = {(49 + 14 + 6)_{10}} = {(69)_{10}}$ M1A1

${5^{{{(126)}_7}}} \equiv {5^{{{(11 \times 6 + 3)}_{10}}}} \equiv {5^{{{(3)}_{10}}}}(\bmod 7)$ M1A1

${5^{{{(3)}_{10}}}} = {(125)_{10}} = {(17 \times 7 + 6)_{10}} \equiv 6(\bmod 7)$ M1A1

hence ${a_0} = 6$ A1

[9 marks]

Examiners report

Questions similar to (a) have been asked in the past so it was surprising to see that solutions this time were generally disappointing.

In (b), most candidates changed the base 7 number 126 to the base 10 number 69. After that the expectation was that Fermat’s little theorem would be used to complete the solution but few candidates actually did that. Many were unable to proceed any further and others used a variety of methods, for example working modulo 7,

${5^{69}} = {({5^2})^{34}}.5 = {4^{34}}.5 = {({4^2})^{17}}.5 = {2^{17}}.5$ etc

This is of course a valid method, but somewhat laborious.

The positive integer N is expressed in base 9 as ${({a_n}{a_{n - 1}} \ldots {a_0})_9}$.

(a) Show that N is divisible by 3 if the least significant digit, ${a_0}$, is divisible by 3.

(b) Show that N is divisible by 2 if the sum of its digits is even.

Markscheme

(a) let $N = {a_n}{a_{n - 1}} \ldots {a_1}{a_0} = {a_n} \times {9^n} + {a_{n - 1}} \times {9^{n - 1}} + \ldots + {a_1} \times 9 + {a_0}$ M1A1

all terms except the last are divisible by 3 and so therefore is their sum R1

it follows that N is divisible by 3 if ${a_0}$ is divisible by 3 AG

[3 marks]

(b) EITHER

consider N in the form

$N = {a_n} \times ({9^n} - 1) + {a_{n - 1}} \times ({9^{n - 1}} - 1) + \ldots + {a_1}(9 - 1) + \sum\limits_{i = 1}^n {{a_i}} $ M1A1

all terms except the last are even so therefore is their sum R1

it follows that N is even if $\sum\limits_{i = 0}^n {{a_i}} $ is even AG

working modulo 2, ${9^k} \equiv 1(\bmod 2)$ M1A1

hence $N = {a_n}{a_{n - 1}} \ldots {a_1}{a_0} = {a_n} \times {9^n} + {a_{n - 1}} \times {9^{n - 1}} + \ldots + {a_1} \times 9 + {a_0} = \sum\limits_{i = 0}^n {{a_i}(\bmod 2)} $ R1

it follows that N is even if $\sum\limits_{i = 0}^n {{a_i}} $ is even AG

[3 marks]

it is divisible by 2 because the sum of the digits is 44 which is even R1

dividing the number by 2 gives ${(232430286)_9}$ M1A1

which is even because the sum of the digits is 30 which is even R1

N is therefore divisible by a further 2 and is therefore divisible by 12 R1

Note: Accept alternative valid solutions.

[6 marks]

Total [12 marks]

Examiners report

Parts (a) and (b) were generally well answered. Part (c), however, caused problems for many candidates with some candidates even believing that showing divisibility by 2 and 3 was sufficient to prove divisibility by 12. Some candidates stated that the fact that the sum of the digits was 44 (which itself is divisible by 4) indicated divisibility by 4 but this was only accepted if the candidates extended their proof in (b) to cover divisibility by 4.

Explaining your method fully, determine whether or not 1189 is a prime number.

[4]

(i) State the fundamental theorem of arithmetic.

(ii) The positive integers M and N have greatest common divisor G and least common multiple L . Show that GL = MN .

[6]

Markscheme

any clearly indicated method of dividing 1189 by successive numbers M1

find that 1189 has factors 29 and/or 41 A2

it follows that 1189 is not a prime number A1

Note: If no method is indicated, award A1 for the factors and A1 for the conclusion.

[4 marks]

(i) every positive integer, greater than 1, is either prime or can be expressed uniquely as a product of primes A1A1

Note: Award A1 for “product of primes” and A1 for “uniquely”.

(ii) METHOD 1

let M and N be expressed as a product of primes as follows

M = AB and N = AC M1A1

where A denotes the factors which are common and B, C the disjoint factors which are not common

it follows that G = A A1

and L = GBC A1

from these equations, it follows that

$GL = A \times ABC = MN$ AG

METHOD 2

Let $M = {2^{{x_1}}} \times {3^{{x_2}}} \times ...p_n^{{x_n}}$ and $N = {2^{{y_1}}} \times {3^{{y_2}}} \times ...p_n^{{y_n}}$ where ${p_n}$ denotes the ${n^{{\text{th}}}}$ prime M1

Then $G = {2^{\min ({x_1},{y_1})}} \times {3^{\min ({x_2},{y_2})}} \times ...p_n^{\min ({x_n},{y_n})}$ A1

and $L = {2^{\max ({x_1},{y_1})}} \times {3^{\max ({x_2},{y_2})}} \times ...p_n^{\max ({x_n},{y_n})}$ A1

It follows that $GL = {2^{{x_1}}} \times {2^{{y_1}}} \times {3^{{x_2}}} \times {3^{{y_2}}} \times ... \times p_n^{{x_n}} \times p_n^{{y_n}}$ A1

= MN AG

[6 marks]

Examiners report

In (a), some candidates tried to use Fermat’s little theorem to determine whether or not 1189 is prime but this method will not always work and in any case the amount of computation involved can be excessive. For this reason, it is strongly recommended that this method should not be used in examinations. In (b), it was clear from the scripts that candidates who had covered this material were generally successful and those who had not previously seen the result were usually unable to proceed.

Andy and Roger are playing tennis with the rule that if one of them wins a game when serving then he carries on serving, and if he loses then the other player takes over the serve.

The probability Andy wins a game when serving is $\frac{1}{2}$ and the probability he wins a game when not serving is $\frac{1}{4}$. Andy serves in the first game. Let ${u_n}$ denote the probability that Andy wins the ${n^{{\text{th}}}}$ game.

State the value of ${u_1}$.

[1]

Show that ${u_n}$ satisfies the recurrence relation

\[{u_n} = \frac{1}{4}{u_{n - 1}} + \frac{1}{4}.\]

[4]

Solve this recurrence relation to find the probability that Andy wins the ${n^{{\text{th}}}}$ game.

[6]

After they have played many games, Pat comes to watch. Use your answer from part (c) to estimate the probability that Andy will win the game they are playing when Pat arrives.

[2]

Markscheme

$\frac{1}{2}$ A1

[1 mark]

Andy could win the ${n^{{\text{th}}}}$ game by winning the $n - {1^{{\text{th}}}}$ and then winning the ${n^{{\text{th}}}}$ game or by losing the $n - {1^{{\text{th}}}}$ and then winning the ${n^{{\text{th}}}}$ (M1)

${u_n} = \frac{1}{2}{u_{n - 1}} + \frac{1}{4}(1 - {u_{n - 1}})$ A1A1M1

Note: Award A1 for each term and M1 for addition of two probabilities.

${u_n} = \frac{1}{4}{u_{n - 1}} + \frac{1}{4}$ AG

[4 marks]

general solution is ${u_n} = A{\left( {\frac{1}{4}} \right)^n} + p(n)$ (M1)

for a particular solution try $p(n) = b$ (M1)

$b = \frac{1}{4}b + \frac{1}{4}$ (A1)

$b = \frac{1}{3}$

hence ${u_n} = A{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$ (A1)

using ${u_1} = \frac{1}{2}$ M1

$\frac{1}{2} = A\left( {\frac{1}{4}} \right) + \frac{1}{3} \Rightarrow A = \frac{2}{3}$

hence ${u_n} = \frac{2}{3}{\left( {\frac{1}{4}} \right)^n} + \frac{1}{3}$ A1

Note: Accept other valid methods.

[6 marks]

for large $n{\text{ }}{u_n} \approx \frac{1}{3}$ (M1)A1

[2 marks]

Total [13 marks]

Examiners report

Not all candidates wrote this answer down correctly although it was essentially told you in the question.

Very badly answered. Candidates seemed to think that they were being told this relationship (so used it to find u(2)) rather than attempting to prove it.

This distinguished the better candidates. Some candidates though that they could use the method for homogeneous recurrence relations of second order and hence started solving a quadratic. Only the better candidates saw that it was a combined AP/GP.

The best candidates saw this but most had not done enough earlier to get to do this.

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

[4]

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

[4]

Explain why each person cannot have shaken hands with exactly nine other people.

[2]

Markscheme

let there be $v$ vertices in the graph; because the graph is simple the degree of each vertex is $ \le v - 1$ A1

the degree of each vertex is $ \ge 1$ A1

there are therefore $v - 1$ possible values for the degree of each vertex A1

given there are $v$ vertices by the pigeon-hole principle there must be at least two with the same degree R1

[4 marks]

consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands M1

the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) A1

every vertex is connected to at least one other vertex as everyone shakes at least one hand A1

the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands R1

Note: Accept answers starting afresh rather than quoting part (a).

[4 marks]

(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number A1

the degree of each vertex would be $9$ and $9 \times 17$ is an odd number (giving a contradiction) A1

[2 marks]

Total [10 marks]

Examiners report

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Markscheme

as each edge contributes 1 to each of the vertices that it is incident with, each edge will contribute 2 to the sum of the degrees of all the vertices (R1)

so $2e = \sum {{\text{degrees}}} $ (A1)

$2e = \frac{{n(n + 1)}}{2}$ A1

$4|n(n + 1)$ A1

n and n + 1 are coprime R1

Note: Accept equivalent reasoning e.g. only one of n and n + 1 can be even.

$4|n{\text{ or }}4|n + 1$ A1

$n \equiv 0(\bmod 4){\text{ or }}n \equiv 3(\bmod 4)$ AG

[6 marks]

since G is simple, the highest degree that a vertex can have is n – 1 R1

the degrees of the vertices must belong to the set $S = \{ 0,{\text{ }}1,{\text{ }}2,{\text{ }} \ldots ,{\text{ }}n - 1\} $ A1

proof by contradiction

if no two vertices have the same degree, all n vertices must have different degrees R1

as there are only n different degrees in set S, the degrees must be precisely the n numbers 0, 1, 2, ..., n – 1 R1

let the vertex with degree 0 be A, then A is not adjacent to any of the other vertices R1

let the vertex with degree n – 1 be B, then B is adjacent to all of the other vertices including A R1R1

this is our desired contradiction, so there must be two vertices of the same degree R1

[8 marks]

Examiners report

Only the top candidates were able to produce logically, well thought-out proofs.

Use the Euclidean algorithm to find $\gcd (752,{\text{ }}352)$.

[4]

A farmer spends £8128 buying cows of two different breeds, A and B, for her farm. A cow of breed A costs £752 and a cow of breed B costs £352.

(i) Set up a diophantine equation to show this.

(ii) Using your working from part (a), find the general solution to this equation.

(iii) Hence find the number of cows of each breed bought by the farmer.

[10]

Markscheme

752 = 2(352) + 48 M1

352 = 7(48) +16 A1

48 = 3(16) A1

therefore $\gcd (752,{\text{ }}352)$ is 16 R1

[4 marks]

(i) let x be the number of cows of breed A

let y be the number of cows of breed B

$752x + 352y = 8128$ A1

(ii) $16|8128$ means there is a solution

$16 = 352 - 7(48)$ (M1)(A1)

$16 = 352 - 7\left( {752 - 2(352)} \right)$

$16 = 15(352) - 7(752)$ (A1)

$8128 = 7620(352) - 3556(752)$

$ \Rightarrow {x_0} = - 3556,{\text{ }}{y_0} = 7620$ (A1)

$ \Rightarrow x = - 3556 + \left( {\frac{{352}}{{16}}} \right)t = - 3556 + 22t$

$ \Rightarrow y = 7620 - \left( {\frac{{752}}{{16}}} \right)t = 7620 - 47t$ M1A1A1

(iii) for x, y to be $ \geqslant 0$, the only solution is t = 162 M1

$ \Rightarrow x = 8,{\text{ }}y = 6$ A1

[10 marks]

Examiners report

Part (a) of this question was the most accessible on the paper and was completed correctly by the majority of candidates. It was pleasing to see that candidates were not put off by the question being set in context and most candidates were able to start part (b). However, a number made errors on the way, quite a number failed to give the general solution and it was only stronger candidates who were able to give a correct solution to part (b) (iii).

The following diagram shows a weighted graph G with vertices A, B, C, D and E.

Show that graph $G$ is Hamiltonian. Find the total number of Hamiltonian cycles in $G$, giving reasons for your answer.

[3]

State an upper bound for the travelling salesman problem for graph $G$.

[1]

Hence find a lower bound for the travelling salesman problem for $G$.

[2]

Show that the lower bound found in (d) cannot be the length of an optimal solution for the travelling salesman problem for the graph $G$.

[3]

Markscheme

eg the cycle ${\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}$ is Hamiltonian A1

starting from any vertex there are four choices

from the next vertex there are three choices, etc … R1

so the number of Hamiltonian cycles is $4!{\text{ }}( = 24)$ A1

Note: Allow 12 distinct cycles (direction not considered) or 60 (if different starting points count as distinct). In any case, just award the second A1 if R1 is awarded.

[3 marks]

total weight of any Hamiltonian cycles stated

eg ${\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}$ has weight $5 + 6 + 7 + 8 + 9 = 35$ A1

[1 mark]

a lower bound for the travelling salesman problem is then obtained by adding the weights of CA and CB to the weight of the minimum spanning tree (M1)

a lower bound is then $14 + 6 + 6 = 26$ A1

[2 marks]

METHOD 1

eg eliminating A from G, a minimum spanning tree of weight 18 is (M1)

adding AD and AB to the spanning tree gives a lower bound of $18 + 4 + 5 = 27 > 26$ A1

so 26 is not the best lower bound AG

Note: Candidates may delete other vertices and the lower bounds obtained are B-28, D-27 and E-28.

METHOD 2

there are 12 distinct cycles (ignoring direction) with the following lengths

Cycle Length

ABCDEA 35 M1

ABCEDA 33

ABDCEA 39

ABDECA 37

ABECDA 31

ABEDCA 31

ACBDEA 37

ACBEDA 29

ACDBEA 35

ACEBDA 33

AEBCDA 31

AECBDA 37 A1

as the optimal solution has length 29 A1

26 is not the best possible lower bound AG

Note: Allow answers where candidates list the 24 cycles obtained by allowing both directions.

[3 marks]

Examiners report

Part (a) was generally well answered, with a variety of interpretations accepted.

Part (b) also had a number of acceptable possibilities.

Part (d) was generally well answered, but there were few good attempts at part (e).

Define what is meant by the statement $x \equiv y(\bmod n){\text{ where }}x{\text{, }}y{\text{, }}n \in {\mathbb{Z}^ + }$ .

[1]

Hence prove that if $x \equiv y(\bmod n)$ then ${x^2} \equiv {y^2}(\bmod n)$ .

[4]

Determine whether or not ${x^2} \equiv {y^2}(\bmod n)$ implies that $x \equiv y(\bmod n)$ .

[4]

Markscheme

$x \equiv y(\bmod n) \Rightarrow x = y + kn,{\text{ }}(k \in \mathbb{Z})$ A1

[1 mark]

$x \equiv y(\bmod n)$

$ \Rightarrow x = y + kn$ M1

${x^2} = {y^2} + 2kny + {k^2}{n^2}$ A1

$ \Rightarrow {x^2} = {y^2} + (2ky + {k^2}n)n$ M1A1

$ \Rightarrow {x^2} \equiv {y^2}(\bmod n)$ AG

[4 marks]

EITHER

${x^2} \equiv {y^2}(\bmod n)$

$ \Rightarrow {x^2} - {y^2} = 0(\bmod n)$ M1

$ \Rightarrow (x - y)(x + y) = 0(\bmod n)$ A1

This will be the case if

$x + y = 0(\bmod n){\text{ or }}x = - y(\bmod n)$ R1

so $x \ne y(\bmod n)$ in general R1

[4 marks]

Any counter example, e.g. $n = 5,{\text{ }}x = 3,{\text{ }}y = 2,$ in which case R2

${x^2} \equiv {y^2}(\bmod n)$ but $x \ne y(\bmod n)$. (false) R1R1

[4 marks]

Examiners report

While most candidates gave a correct meaning to $x \equiv y(\bmod n)$ , there were some incorrect statements, the most common being $x \equiv y(\bmod n)$ means that when x is divided by n, there is a remainder y. The true statement $8 \equiv 5(\bmod 3)$ shows that this statement is incorrect. Part (b) was solved successfully by many candidates but (c) caused problems for some candidates who thought that the result in (c) followed automatically from the result in (b).

Convert the decimal number 51966 to base 16.

[4]

(i) Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and 612.

(ii) Find integers p and q such that 901p + 612q = d .

(iii) Find the least possible positive integers s and t such that 901s − 612t = 85.

[10]

In each of the following cases find the solutions, if any, of the given linear congruence.

(i) $9x \equiv 3(\bmod 18)$

(ii) $9x \equiv 3(\bmod 15)$

[5]

Markscheme

the relevant powers of 16 are 16, 256 and 4096

then

$51966 = 12 \times 4096{\text{ remainder }}2814$ M1A1

$2814 = 10 \times 256{\text{ remainder }}254$

$254 = 15 \times 16{\text{ remainder }}14$ A1

the hexadecimal number is CAFE A1

Note: CAFE is produced using a standard notation, accept explained alternative notations.

[4 marks]

(i) using the Euclidean Algorithm (M1)

$901 = 612 + 289$ (A1)

$612 = 2 \times 289 + 34$

$289 = 8 \times 34 + 17$

$\gcd (901,{\text{ }}612) = 17$ A1

(ii) working backwards (M1)

$17 = 289 - 8 \times 34$

$ = 289 - 8 \times (612 - 2 \times 289)$

$ = 17 \times (901 - 612) - 8 \times 612$

$ = 27 \times 901 - 25 \times 612$

${\text{so }}p = 17,{\text{ }}q = - 25$ A1A1

(iii) a particular solution is

$s = 5p = 85,{\text{ }}t = - 5q = 125$ (A1)

the general solution is

$s = 85 + 36\lambda ,{\text{ }}t = 125 + 53\lambda $ M1A1

by inspection the solution satisfying all conditions is

$(\lambda = - 2),{\text{ }}s = 13,{\text{ }}t = 19$ A1

[10 marks]

(i) the congruence is equivalent to $9x = 3 + 18\lambda $ (A1)

this has no solutions as 9 does not divide the RHS R1

(ii) the congruence is equivalent to $3x = 1 + 5\lambda ,{\text{ }}\left( {3x \equiv 1(\bmod 5)} \right)$ A1

one solution is $x = 2$ , so the general solution is $x = 2 + 5n\,\,\,\,\,\left( {x \equiv 2(\bmod 5)} \right)$ M1A1

[5 marks]

Examiners report

Many did not seem familiar with hexadecimal notation and often left their answer as 12101514 instead of CAFE.

The Euclidean algorithm was generally found to be easy to deal with but getting a general solution in part (iii) eluded many candidates.

Rewriting the congruence in the form $9x = 3 + 18\lambda $ for example was not often seen but should have been the first thing thought of.

Given that $a,{\text{ }}b,{\text{ }}c,{\text{ }}d \in \mathbb{Z}$, show that

\[(a - b)(a - c)(a - d)(b - c)(b - d)(c - d) \equiv 0(\bmod 3).\]

Markscheme

EITHER

we work modulo 3 throughout

the values of a, b, c, d can only be 0, 1, 2 R2

since there are 4 variables but only 3 possible values, at least 2 of the variables must be equal $(\bmod 3)$ R2

therefore at least 1 of the differences must be $0(\bmod 3)$ R2

the product is therefore $0(\bmod 3)$ R1AG

we attempt to find values for the differences which do not give $0(\bmod 3)$ for the product

we work modulo 3 throughout

we note first that none of the differences can be zero R1

a − b can therefore only be 1 or 2 R1

suppose it is 1, then b − c can only be 1

since if it is 2, $(a - b) + (b - c) \equiv 3 \equiv 0(\bmod 3)$ R1

c − d cannot now be 1 because if it is

$(a - b) + (b - c) + (c - d) = a - d \equiv 3 \equiv 0(\bmod 3)$ R1

c − d cannot now be 2 because if it is

$(b - c) + (c - d) = b - d \equiv 3 \equiv 0(\bmod 3)$ R1

we cannot therefore find values of c and d to give the required result R1

a similar argument holds if we suppose a − b is 2, in which case b − c must be 2 and we cannot find a value of c − d R1

the product is therefore $0(\bmod 3)$ AG

[7 marks]

Examiners report

Most candidates who solved this question used the argument that there are four variables which can take only one of three different values modulo 3 so that at least two must be equivalent modulo 3 which leads to the required result. This apparently simple result, however, requires a fair amount of insight and few candidates managed it.

The sequence $\{ {u_n}\} $ , $n \in {\mathbb{Z}^ + }$ , satisfies the recurrence relation ${u_{n + 2}} = 5{u_{n + 1}} - 6{u_n}$ .

Given that ${u_1} = {u_2} = 3$ , obtain an expression for ${u_n}$ in terms of n .

[6]

The sequence $\{ {v_n}\} $ , $n \in {\mathbb{Z}^ + }$ , satisfies the recurrence relation ${v_{n + 2}} = 4{v_{n + 1}} - 4{v_n}$ .

Given that ${v_1} = 2$ and ${v_2} = 12$ , use the principle of strong mathematical induction to show that ${v_n} = {2^n}(2n - 1)$ .

[8]

Markscheme

the auxiliary equation is

${m^2} - 5m + 6 = 0$ M1

giving $m = 2,{\text{ 3}}$ A1

the general solution is

${u_n} = A \times {2^n} + B \times {3^n}$ A1

substituting n = 1, 2

$2A + 3B = 3$ M1

$4A + 9B = 3$ A1

the solution is A = 3, B = –1 giving ${u_n} = 3 \times {2^n} - {3^n}$ A1

[6 marks]

we first prove that ${v_n} = {2^n}(2n - 1)$ for n = 1, 2 M1

for n = 1, it gives $2 \times 1 = 2$ which is correct

for n = 2 , it gives $4 \times 3 = 12$ which is correct A1

we now assume that the result is true for $n \leqslant k$ M1

consider

${v_{k + 1}} = 4{v_k} - 4{v_{k - 1}}{\text{ }}(k \geqslant 2)$ M1

$ = {4.2^k}(2k - 1) - {4.2^{k - 1}}(2k - 3)$ A1

$ = {2^{k + 1}}(4k - 2 - 2k + 3)$ A1

$ = {2^{k + 1}}\left( {2(k + 1) - 1} \right)$ A1

this proves that if the result is true for $n \leqslant k$ then it is true for $n \leqslant k + 1$

since we have also proved it true for $n \leqslant 2$ , the general result is proved by induction R1

Note: A reasonable attempt has to be made to the induction step for the final R1 to be awarded.

[8 marks]

Examiners report

[N/A]

State the Fundamental theorem of arithmetic for positive whole numbers greater than $1$.

[2]

Use the Fundamental theorem of arithmetic, applied to $5577$ and $99\,099$, to calculate $\gcd (5577,{\text{ }}99\,099)$ and ${\text{lcm}}(5577,{\text{ }}99\,099)$, expressing each of your answers as a product of prime numbers.

[3]

Prove that $\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$ for all $n,{\text{ }}m \in {\mathbb{Z}^ + }$.

[6]

Markscheme

every positive integer, greater than $1$, is either prime or can be expressed uniquely as a product of primes A1A1

Note: Award A1 for “product of primes” and A1 for “uniquely”.

[2 marks]

$5577 = 3 \times 11 \times {13^2}{\text{ and }}99099 = {3^2} \times 7 \times {11^2} \times 13$ M1

$\gcd (5577,{\text{ }}99099) = 3 \times 11 \times 13,{\text{ lcm}}(5577,{\text{ }}99099) = {3^2} \times 7 \times {11^2} \times {13^2}$ A1A1

[3 marks]

METHOD 1

$n = p_1^{{k_1}}p_2^{{k_2}} \ldots p_r^{{k_r}}$ and $m = p_1^{{j_1}}p_2^{{j_2}} \ldots p_r^{{j_r}}$ M1

employing all the prime factors of $n$ and $m$, and inserting zero exponents if necessary R1

define ${g_i} = \min ({k_i},{\text{ }}{j_i})$ and ${h_i} = \max ({k_i},{\text{ }}{j_i})$ for $i = 1 \ldots r$ (M1)

$\gcd (n,{\text{ }}m) = p_1^{{g_1}}p_2^{{g_2}} \ldots p_r^{{g_r}}$ and ${\text{lcm}}(n,{\text{ }}m) = p_1^{{h_1}}p_2^{{h_2}} \ldots p_r^{{h_r}}$ A1A1

noting that ${g_i} + {h_i} = {k_i} + {j_i}$ for $i = 1 \ldots r$ R1

$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$ for all $n,{\text{ }}m \in {\mathbb{Z}^ + }$AG

METHOD 2

let $m$ and $n$ be expressed as a product of primes where $m = ab$ and $n = ac$ M1

$a$ denotes the factors that are common and $b,{\text{ }}c$ are the disjoint factors that are not common R1

$\gcd (n,{\text{ }}m) = a$ A1

${\text{lcm}}(n,{\text{ }}m) = \gcd (n,{\text{ }}m)bc$ A1

$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = a \times (abc)$ M1

$ = ab \times ac$ and $m = ab$ and $n = ac$ so R1

$\gcd (n,{\text{ }}m) \times 1{\text{ cm}}(n,{\text{ }}m) = n \times m$ for all $n,{\text{ }}m \in {\mathbb{Z}^ + }$ AG

[6 marks]

Total [11 marks]

Examiners report

In part (a), most candidates omitted the 'uniquely' in their definition of the fundamental theorem of arithmetic. A few candidates defined what a prime number is.

In part (b), a substantial number of candidates used the Euclidean algorithm rather than the fundamental theorem of arithmetic to calculate $\gcd (5577,{\text{ }}99099)$ and ${\text{lcm}}(5577,{\text{ }}99099)$.

In part (c), a standard proof that has appeared in previous examination papers, was answered successfully by candidates who were well prepared.

The following figure shows the floor plan of a museum.

(a) (i) Draw a graph G that represents the plan of the museum where each exhibition room is represented by a vertex labelled with the exhibition room number and each door between exhibition rooms is represented by an edge. Do not consider the entrance foyer as a museum exhibition room.

(ii) Write down the degrees of the vertices that represent each exhibition room.

(iii) Virginia enters the museum through the entrance foyer. Use your answers to (i) and (ii) to justify why it is possible for her to visit the thirteen exhibition rooms going through each internal doorway exactly once.

(b) Let G and H be two graphs whose adjacency matrices are represented below.

Using the adjacency matrices,

(i) find the number of edges of each graph;

(ii) show that exactly one of the graphs has a Eulerian trail;

(iii) show that neither of the graphs has a Eulerian circuit.

Markscheme

(a) (i)
(M1)A1

Note: Do not penalize candidates who include the entrance foyer.

(ii) the degrees of the vertices are 4, 2, 4, 4, 2, 2, 4, 2, 2, 2, 2, 2, 2 A1

(iii) the degree of all vertices is even and hence a Eulerian circuit exists, A1

hence it is possible to enter the museum through the foyer and visit each room 1–13 going through each internal doorway exactly once AG

Note: The connected graph condition is not required.

[4 marks]

(b) (i)
(M1)

graph G has 15 edges and graph H has 22 edges A1A1

(ii) the degree of every vertex is equal to the sum of the numbers in the corresponding row (or column) of the adjacency table

exactly two of the vertices of G have an odd degree (B and C) A1

H has four vertices with odd degree A1

G is the graph that has a Eulerian trail (and H does not) R1

(iii) neither graph has all vertices of even degree R1

therefore neither of them has a Eulerian circuit AG

[7 marks]

Examiners report

Part (a) was generally well answered. There were many examples of full marks in this part. Part (b) caused a few more difficulties, although there were many good solutions. Few candidates used the matrix to find the number of edges, preferring instead to draw the graph. A surprising number of students confused the ideas of having vertices of odd degree.

Show that $30$ is a factor of ${n^5} - n$ for all $n \in \mathbb{N}$.

[5]

(i) Show that ${3^{{3^m}}} \equiv 3({\text{mod}}4)$ for all $m \in \mathbb{N}$.

(ii) Hence show that there is exactly one pair $(m,{\text{ }}n)$ where $m,{\text{ }}n \in \mathbb{N}$, satisfying the equation ${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$.

[8]

Markscheme

METHOD 1

${n^5} - n = \underbrace {n(n - 1)(n + 1)}_{{\text{3 consecutive integers}}}({n^2} + 1) \equiv 0({\text{mod}}6)$ M1

at least a factor is multiple of 3 and at least a factor is multiple of 2 R1

${n^5} - n = n({n^4} - 1) \equiv 0({\text{mod}}5)$ as ${n^4} \equiv 1({\text{mod}}5)$ by FLT R1

therefore, as ${\text{(5, 6)}} = 1$, R1

${n^5} - n \equiv 0\left( {\bmod \underbrace {5 \times 6}_{30}} \right)$ A1

ie 30 is a factor of ${n^5} - n$ AG

METHOD 2

let ${\text{P}}(n)$ be the proposition: ${n^5} - n = 30\alpha $ for some $\alpha \in \mathbb{Z}$

${0^5} - 0 = 30 \times 0$, so ${\text{P}}(0)$ is true A1

assume ${\text{P}}(k)$ is true for some $k$ and consider ${\text{P}}(k + 1)$

${(k + 1)^5} - (k + 1) = {k^5} + 5{k^4} + 10{k^3} + 10{k^2} + 5k + 1 - k - 1$ M1

$ = ({k^5} - k) + 5k\left( {\underbrace {{k^3} + 3{k^2} + 3k + 1}_{{{(k + 1)}^3}} - ({k^2} + k)} \right)$

$ = ({k^5} - k) + 5k\left( {{{(k + 1)}^3} - k(k + 1)} \right)$

$ = 30\alpha + \underbrace {5k(k + 1)\left( {\underbrace {{k^2} + k + 1}_{k(k + 1) + 1}} \right)}_{{\text{multiple of 6}}}$ M1

$ = 30\alpha + 30\beta $ A1

as ${\text{P}}(0)$ is true and ${\text{P}}(k)$ true implies ${\text{P}}(k + 1)$ true, by PMI ${\text{P}}(n)$ is true for all values $n \in \mathbb{N}$ R1

Note: Award the first M1 only if the correct induction procedure is followed and the correct first line is seen.

Note: Award R1 only if both M marks have been awarded.

METHOD 3

${n^5} - n = n({n^4} - 1)$ M1

$ = n({n^2} - 1)({n^2} + 1)$ A1

$ = (n - 1)n(n + 1)({n^2} - 4 + 5)$ R1

$ = (n - 2)(n - 1)n(n + 1)(n + 2) + 5(n - 1)n(n + 1)$ A1

each term is multiple of 2, 3 and 5 R1

therefore is divisible by 30 AG

[5 marks]

(i) METHOD 1

case 1: $m = 0$ and ${3^{{3^0}}} \equiv 3{\text{mod}}4$ is true A1

case 2: $m > 0$

let $N = {3^m} \geqslant 3$ and consider the binomial expansion M1

${3^N} = {(1 + 2)^N} = \sum\limits_{k = 0}^N {} $ $\left( \begin{array}{c}N\\k\end{array} \right){2^k} = 1 + 2N + \underbrace {\sum\limits_{k = 2}^N {\left( \begin{array}{c}N\\k\end{array} \right){2^k}} }_{ \equiv ({\text{mod}}4)} \equiv 1 + 2N({\text{mod}}4)$ A1

as $\underbrace {{3^m}}_N \equiv {( - 1)^m}({\text{mod}}4) \Rightarrow 1 + 2N \equiv 1 + 2{( - 1)^m}({\text{mod}}4)$ R1

therefore $\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv 1 + 2{( - 1)^m}({\text{mod}}4) \Rightarrow $ $\left\{ \begin{array}{l}\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 + 2}_3({\text{mod}}4){\rm{for\,}} m {\rm{\,even}}\\\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 - 2}_{ - 1 \equiv 3({\text{mod}}4)}({\text{mod}}4){\rm{for\,}} m {\rm{\,odd}}\end{array} \right.$ R1

which proves that ${3^{{3^m}}} \equiv 3({\text{mod}}4)$ for any $m \in \mathbb{N}$ AG

METHOD 2

let ${\text{P}}(n)$ be the proposition: ${3^{{3^n}}} - 3 \equiv 0({\text{mod }}4,{\text{ or }}24)$

${3^{{3^0}}} - 3 = 3 - 3 \equiv 0({\text{mod }}4{\text{ or }}24)$, so ${\text{P}}(0)$ is true A1

assume ${\text{P}}(k)$ is true for some $k$ M1

consider ${3^{{3^{^{k + 1}}}}} - 3 = {3^{{3^k} \times 3}} - 3$ M1

$ = {(3 + 24r)^3} - 3$

$ \equiv 27 + 24t - 3$ R1

$ \equiv 0({\text{mod }}4{\text{ or }}24)$

as ${\text{P}}(0)$ is true and ${\text{P}}(k)$ true implies ${\text{P}}(k + 1)$ true, by PMI ${\text{P}}(n)$ is true for all values $n \in \mathbb{N}$ R1

METHOD 3

${3^{{3^m}}} - 3 = 3({3^{{3^m} - 1}} - 1)$ M1A1

$ = 3({3^{2k}} - 1)$ R1

$ = 3({9^k} - 1)$

$ = 3\underbrace {\left( {{{(8 + 1)}^k} - 1} \right)}_{{\text{multiple of 8}}}$ R1

$ \equiv 0({\text{mod}}24)$ A1

which proves that ${3^{{3^m}}} \equiv 3({\text{mod}}4)$ for any $m \in \mathbb{N}$ AG

(ii) for $m \in \mathbb{N},{\text{ }}{3^{{3^m}}} \equiv 3({\text{mod}}4)$ and, as ${2^{{2^n}}} \equiv 0({\text{mod}}4)$ and ${5^2} \equiv 1({\text{mod}}4)$ then ${2^{{2^n}}} + {5^2} \equiv 1({\text{mod}}4)$ for $n \in {\mathbb{Z}^ + }$

there is no solution to ${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$ for pairs $(m,{\text{ }}n) \in \mathbb{N} \times {\mathbb{Z}^ + }$ R1

when $n = 0$, we have ${3^{{3^m}}} = {2^{{2^0}}} + {5^2} \Rightarrow {3^{{3^m}}} = 27 \Rightarrow m = 1$ M1

therefore $(m,{\text{ }}n) = (1,{\text{ }}0)$ A1

is the only pair of non-negative integers that satisfies the equation AG

[8 marks]

Examiners report

Many students were able to get partial credit for part (a), although few managed to gain full marks.

There seemed to be very few good attempts at part (b), many failing at the outset to understand what was meant by ${3^{{3^m}}}$.

(a) Draw a spanning tree for

(i) the complete graph, ${K_4}$;

(ii) the complete bipartite graph, ${K_{4,4}}$.

(b) Prove that a simple connected graph with n vertices, where $n > 1$, must have two vertices

of the same degree.

Markscheme

(a) (i)
A1

Note: Or equivalent not worrying about the orientation.

(ii)
A1

Note: Other trees are possible, but must clearly come from the bipartite graph, so, for example, a straight line graph is not acceptable unless the bipartite nature is clearly shown eg, with black and white vertices.

[2 marks]

(b) graph is simple implies maximum degree is $n - 1$ A1

graph is connected implies minimum degree is 1 A1

by a pigeon-hole principle two vertices must have the same degree R1

[3 marks]

remove one edge of this cycle M1

the graph remains connected A1

repeat until there are no cycles M1

the final graph is connected and has no cycles A1

so is a tree AG

Note: Allow other methods eg, induction, reference to Kruskal’s algorithm.

[5 marks]

Total [10 marks]

Examiners report

[N/A]

The weights of the edges in the complete graph $G$ are shown in the following table.

M16/5/MATHL/HP3/ENG/TZ0/DM/02

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $G$.

[5]

By first removing A , use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for $G$.

[7]

Markscheme

attempt to use the nearest neighbour algorithm M1

$\begin{array}{*{20}{l}} {{\text{the nearest neighbour path is}}}&{{\text{A}} \to {\text{D}} \to {\text{C }}A1} \\ {}&{ \to {\text{E}} \to {\text{B}} \to {\text{F}} \to {\text{A }}A1} \end{array}$

the upper bound is the total weight of this path, ie (M1)

$8 + 7 + 8 + 10 + 13 + 9 = 55$ A1

Note: The (M1) is for adding 6 weights together.

[5 marks]

attempt to use an appropriate algorithm, with A deleted, to determine the minimum spanning tree, eg Kruskal’s (M1)

CD (7) A1

CE, CB (8,9) A1

DF or EF (11) A1

the weight of this minimum spanning tree is 35 (A1)

adding in the two smallest weights joining A (AD and AF) to this tree gives a lower bound (M1)

of $35 + 8 + 9 = 52$ A1

Note: Clear diagrams aiding solutions are acceptable in (a) and (b).

[7 marks]

Examiners report

Generally good use of the nearest neighbour algorithm. Some candidates showed no knowledge of it and there was some confusion with the twice the weight of a minimal spanning tree method. Some candidates forgot to go back to A and thus did not have a Hamiltonian cycle.

The method was generally known. Some candidates used nearest neighbour instead of Kruskal’s algorithm to find a minimal spanning tree. Some forgot to add in the two edges connected to . Some with the right method made mistakes in not noticing the correct edge to choose. A

The following graph represents the cost in dollars of travelling by bus between 10 towns in a particular province.

Use Dijkstra’s algorithm to find the cheapest route between $A$ and $J$, and state its cost.

[7]

For the remainder of the question you may find the cheapest route between any two towns by inspection.

It is given that the total cost of travelling on all the roads without repeating any is $\$ 139$.

A tourist decides to go over all the roads at least once, starting and finishing at town $A$.

Find the lowest possible cost of his journey, stating clearly which roads need to be travelled more than once. You must fully justify your answer.

[6]

Markscheme

M1A1A1A1

(M1 for an attempt at Dijkstra’s)

(A1 for value of ${\text{D}} = 17$)

(A1 for value of ${\text{H}} = 22$)

(A1 for value of ${\text{G}} = 22$)

route is $ABDHJ$ (M1)A1

cost is $$27$ A1

Note: Accept other layouts.

[7 marks]

there are 4 odd vertices $A$, $D$, $F$ and $J$ A1

these can be joined up in 3 ways with the following extra costs

$AD$ and $FJ$$\;\;\;17 + 13 = 30$

$AF$ and $DJ$$\;\;\;23 + 10 = 33$

$AJ$ and $DF$$\;\;\;27 + 12 = 39$ M1A1A1

Note: Award M1 for an attempt to find different routes.

Award A1A1 for correct values for all three costs A1 for one correct.

need to repeat $AB$, $BD$, $FG$ and $GJ$ A1

total cost is $139 + 30 = \$ 169$ A1

[6 marks]

Total [13 marks]

Examiners report

Many candidates had the correct route and the cost. Not all showed sufficient working with their Dijkstra’s algorithm. See the mark-scheme for the neat way of laying out the working, including the back-tracking method. This tabular working is efficient, avoids mistakes and saves time.

There was often confusion here between this problem and the travelling salesman. Good candidates started with the number of vertices of odd degree. Weaker candidates just tried to write the answer down without complete reasoning. All the 3 ways of joining the odd vertices had to be considered so that you knew you had the smallest. Sometimes a mark was lost by giving which routes (paths) had to be repeated rather than which roads (edges).

Use the Euclidean algorithm to find the greatest common divisor of 259 and 581.

[4]

Hence, or otherwise, find the general solution to the diophantine equation 259x + 581y = 7 .

[5]

Markscheme

$581 = 2 \times 259 + 63$ M1A1

$259 = 4 \times 63 + 7$ A1

$63 = 9 \times 7$

the GCD is therefore 7 A1

[4 marks]

consider

$7 = 259 - 4 \times 63$ M1

$ = 259 - 4 \times (581 - 2 \times 259)$ A1

$ = 259 \times 9 + 581 \times ( - 4)$ A1

the general solution is therefore

$x = 9 + 83n;{\text{ }}y = - 4 - 37n{\text{ where }}n \in \mathbb{Z}$ M1A1

Notes: Accept solutions laid out in tabular form. Dividing the diophantine equation by 7 is an equally valid method.

[5 marks]

Examiners report

[N/A]

An arithmetic sequence has first term 2 and common difference 4. Another arithmetic sequence has first term 7 and common difference 5. Find the set of all numbers which are members of both sequences.

Markscheme

the mth term of the first sequence $ = 2 + 4(m - 1)$ (M1)(A1)

the nth term of the second sequence $ = 7 + 5(n - 1)$ (A1)

EITHER

equating these, M1

$5n = 4m - 4$

$5n = 4(m - 1)$ (A1)

4 and 5 are coprime (M1)

$ \Rightarrow 4|n$ so $n = 4s$ or $5|(m - 1)$ so $m = 5s + 1$ , $s \in {\mathbb{Z}^ + }$ (A1)A1

thus the common terms are of the form $\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} $ A1

the numbers of both sequences are

2, 6, 10, 14, 18, 22

7, 12, 17, 22 A1

so 22 is common A1

identify the next common number as 42 (M1)A1

the general solution is $\{ 2 + 20s;{\text{ }}s \in {\mathbb{Z}^ + }\} $ (M1)A1

[9 marks]

Examiners report

Solutions to this question were extremely variable with some candidates taking several pages to give a correct solution and others taking several pages and getting nowhere. Some elegant solutions were seen including the fact that the members of the two sets can be represented as $2\bmod 4$ and $2\bmod 5$ respectively so that common members are $2\bmod 20$.

Using the Euclidean algorithm, show that $\gcd (99,{\text{ }}332) = 1$.

[4]

(i) Find the general solution to the diophantine equation $332x - 99y = 1$.

(ii) Hence, or otherwise, find the smallest positive integer satisfying the congruence $17z \equiv 1(\bmod 57)$.

[11]

Markscheme

using the Euclidean Algorithm,

$332 = 3 \times 99 + 35{\text{ }}$ M1

$99 = 2 \times 35 + 29$ A1

$35 = 1 \times 29 + 6$

$29 = 4 \times 6 + 5$ A1

$6 = 1 \times 5 + 1$ A1

hence 332 and 99 have a gcd of 1 AG

Note: For both (a) and (b) accept layout in tabular form, especially the brackets method of keeping track of the linear combinations as the method proceeds.

[4 marks]

(i) working backwards, (M1)

$6 - 5 = 1$

$6 - (29 - 4 \times 6) = 1{\text{ or }}5 \times 6 - 29 = 1$ A1

$5 \times (35-29)-29 = 1{\text{ or }}5 \times 35-6 \times 29 = 1$ A1

$5 \times 35-6 \times (99-2 \times 35) = 1{\text{ or }}17 \times 35-6 \times 99 = 1$

$17 \times (332-3 \times 99)-6 \times 99 = 1{\text{ or }}17 \times 332-57 \times 99 = 1$ A1

a solution to the Diophantine equation is therefore

$x = 17,{\text{ }}y = 57$ (A1)

the general solution is

$x = 17 + 99N,{\text{ }}y = 57 + 332N$ A1A1

Note: If part (a) is wrong it is inappropriate to give FT in (b) as the numbers will contradict, however the M1 can be given.

(ii) it follows from previous work that

$17 \times 332 = 1 + 99 \times 57$ (M1)

$ \equiv 1(\bmod 57)$ (A1)

z = 332 is a solution to the given congruence (A1)

the general solution is 332 + 57N so the smallest solution is 47 A1

[11 marks]

Examiners report

Part (a) was well answered and (b) fairly well answered. There were problems with negative signs due to the fact that there was a negative in the question, so candidates had to think a little, rather than just remembering formulae by rote. The lay-out of the algorithm that keeps track of the linear combinations of the first 2 variables is recommended to teachers.

Solve, by any method, the following system of linear congruences

$x \equiv 9(\bmod 11)$

$x \equiv 1(\bmod 5)$

[3]

Find the remainder when ${41^{82}}$ is divided by 11.

[4]

Using your answers to parts (a) and (b) find the remainder when ${41^{82}}$ is divided by $55$.

[3]

Markscheme

METHOD 1

listing $9,{\rm{ }}20,{\rm{ }}31$, $ \ldots $ and $1,{\rm{ }}6,11,16,{\rm{ }}21,{\rm{ }}26,{\rm{ }}31$, $ \ldots $ M1

one solution is $31$ (A1)

by the Chinese remainder theorem the full solution is

$x \equiv 31(\bmod 55)$ A1 N2

METHOD 2

$x \equiv 9(\bmod 11) \Rightarrow x = 9 + 11t$ M1

$ \Rightarrow 9 + 11t \equiv 1(\bmod 5)$

$ \Rightarrow t \equiv 2(\bmod 5)$ A1

$ \Rightarrow t = 2 + 5s$

$ \Rightarrow x = 9 + 11(2 + 5s)$

$ \Rightarrow x = 31 + 55s{\text{ }}\left( { \Rightarrow x \equiv 31(\bmod 55)} \right)$ A1

Note: Accept other methods eg formula, Diophantine equation.

Note: Accept other equivalent answers e.g. $ - 79(\bmod 55)$.

[3 marks]

${41^{82}} \equiv {8^{82}}(\bmod 11)$

by Fermat’s little theorem ${8^{10}} \equiv 1(\bmod 11)\;\;\;\left( {{\text{or }}{{41}^{10}} \equiv 1(\bmod 11)} \right)$ M1

${8^{82}} \equiv {8^2}(\bmod 11)$ M1

$ \equiv 9(\bmod 11)$ (A1)

remainder is $9$ A1

Note: Accept simplifications done without Fermat.

[4 marks]

${41^{82}} \equiv {1^{82}} \equiv 1(\bmod 5)$ A1

so ${41^{82}}$ has a remainder $1$ when divided by $5$ and a remainder $9$ when divided by $11$ R1

hence by part (a) the remainder is $31$ A1

[3 marks]

Total [10 marks]

Examiners report

A variety of methods were used here. The Chinese Remainder Theorem method (Method 2 on the mark-scheme) is probably the most instructive. Candidates who tried to do it by formula often (as usual) made mistakes and got it wrong. Marks were lost by just saying 31 and not giving mod (55).

Time was lost here by not using Fermat’s Little Theorem as a starting point, although the ad hoc methods will work.

Although it said use parts (a) and (b) not enough candidates saw the connection.

Consider an integer $a$ with $(n + 1)$ digits written as $a = {10^n}{a_n} + {10^{n - 1}}{a_{n - 1}} + \ldots + 10{a_1} + {a_0}$, where $0 \leqslant {a_i} \leqslant 9$ for $0 \leqslant i \leqslant n$, and ${a_n} \ne 0$.

(a) Show that $a \equiv ({a_n} + {a_{n - 1}} + \ldots + {a_0}) ({\text{mod9}})$.

(b) Hence find all pairs of values of the single digits $x$ and $y$ such that the number $a = 476x212y$ is a multiple of $45$.

(ii) Hence find ${b^2}$ in base 9, by performing all the calculations without changing base.

Markscheme

(a) $10 \equiv 1(\bmod 9) \Rightarrow {10^i} \equiv 1({\text{mod9}}),{\text{ }}i = 1,{\text{ }} ... ,{\text{ }}n$ M1A1

$ \Rightarrow {10^i}{a_i} \equiv {a_i}({\text{mod9}}),{\text{ }}i = 1,{\text{ }}n$ M1

Note: Allow $i = 0$ but do not penalize its omission.

$ \Rightarrow ({10^n}{a_n} + {10^{n - 1}}{a_{n - 1}} + \ldots + {a_0}) \equiv ({a_n} + {a_{n - 1}} + \ldots + {a_0})({\text{mod9}})$ AG

[3 marks]

(b) $4 + 7 + 6 + x + 2 + 1 + 2 + y = 9k,{\text{ }}k \in \mathbb{Z}$ (M1)

$ \Rightarrow (22 + x + y) \equiv 0(\bmod 9),{\text{ }} \Rightarrow (x + y) \equiv 5({\text{mod9}})$

$ \Rightarrow x + y = 5$ or $14$ A1

if $5$ divides $a$, then $y = 0$ or $5$ M1

so $y = 0 \Rightarrow x = 5,{\text{ }}\left( {ie{\text{ }}(x,{\text{ }}y) = (5,{\text{ }}0)} \right)$ A1

$y = 5 \Rightarrow x = 0$ or $x = 9,{\text{ }}\left( {ie{\text{ }}(x,{\text{ }}y) = (0,{\text{ }}5){\text{ or }}(x,{\text{ }}y) = (9,{\text{ }}5)} \right)$ A1A1

[6 marks]

$b = {(52\,151)_9}$ AG

(ii)
M1A3

Note: M1 for attempt, A1 for two correct lines of multiplication, A2 for two correct lines of multiplication and a correct addition, A3 for all correct.

[6 marks]

Examiners report

Surprisingly few good answers. Part (a) had a number of correct solutions, but there were also many that seemed to be a memorised solution, not properly expressed – and consequently wrong. In part (b) many failed to understand the question, not registering that x and y were digits rather than numbers. Part (c)(i) was generally well answered, although there were a number of longer methods applied, and few managed to do (c)(ii).

(a) Find the general solution for the following system of congruences.

$N \equiv 3(\bmod 11)$

$N \equiv 4(\bmod 9)$

$N \equiv 0(\bmod 7)$

(b) Find all values of N such that $2000 \leqslant N \leqslant 4000$.

Markscheme

(a) $N = 3 + 11t$ M1

$3 + 11t \equiv 4(\bmod 9)$

$2t \equiv 1(\bmod 9)$ (A1)

multiplying by 5, $10t \equiv 5(\bmod 9)$ (M1)

$t \equiv 5(\bmod 9)$ A1

$t = 5 + 9s$ M1

$N = 3 + 11(5 + 9s)$

$N = 58 + 99s$ A1

$58 + 99s \equiv 0(\bmod 7)$

$2 + s \equiv 0(\bmod 7)$

$s \equiv 5(\bmod 7)$ A1

$s = 5 + 7u$ M1

$N = 58 + 99(5 + 7u)$

$N = 553 + 693u$ A1

Note: Allow solutions that are done by formula or an exhaustive, systematic listing of possibilities.

[9 marks]

(b) u = 3 or 4

hence N = 553 + 2079 = 2632 or N = 553 + 2772 = 3325 A1A1

[2 marks]

Total [11 marks]

Examiners report

This was a standard Chinese remainder theorem problem that many candidates gained good marks on. Some candidates employed a formula, which was fine if they remembered it correctly (but not all did), although it did not always show good understanding of the problem.

Anna is playing with some cars and divides them into three sets of equal size. However, when she tries to divide them into five sets of equal size, there are four left over. Given that she has fewer than 50 cars, what are the possible numbers of cars she can have?

Markscheme

METHOD 1

let x be the number of cars

we know $x \equiv 0(\bmod 3)$ (A1)

also $x \equiv 4(\bmod 5)$ (A1)

so $x = 3t \Rightarrow 3t \equiv 4(\bmod 5)$ M1

$ \Rightarrow 6t \equiv 8(\bmod 5)$

$ \Rightarrow t \equiv 3(\bmod 5)$

$ \Rightarrow t = 3 + 5s$

$ \Rightarrow x = 9 + 15s$ A1

since there must be fewer than 50 cars, x = 9, 24, 39 A1A1A1

Note: Only award two of the final three A1 marks if more than three solutions are given.

[7 marks]

METHOD 2

x is a multiple of 3 that ends in 4 or 9 R4

therefore x = 9, 24, 39 A1A1A1 N3

Note: Only award two of the final three A1 marks if more than three solutions are given.

[7 marks]

Examiners report

There were a number of totally correct solutions to this question, but some students were unable to fully justify their results.

Consider the integers $a = 871$ and $b= 1157$, given in base $10$.

(i) Express $a$ and $b$ in base $13$.

(ii) Hence show that ${\text{gcd}}(a,{\text{ }}b) = 13$.

[7]

A list $L$ contains $n+ 1$ distinct positive integers. Prove that at least two members of $L$leave the same remainder on division by $n$.

[4]

Consider the simultaneous equations

$4x + y + 5z = a$

$2x + z = b$

$3x + 2y + 4z = c$

where $x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}$.

(i) Show that 7 divides $2a + b - c$.

(ii) Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

[6]

Consider the set $P$ of numbers of the form ${n^2} - n + 41,{\text{ }}n \in \mathbb{N}$.

(i) Prove that all elements of P are odd.

(ii) List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii) Show that not all elements of P are prime.

[6]

Markscheme

(i) METHOD 1

using a relevant list of powers of 13: (1), 13, 169, (2197) M1

$871 = 5 \times {13^2} + 2 \times 13$ A1

$871 = {520_{13}}$ A1

$1157 = 6 \times {13^2} + 11 \times 13$ A1

$1157 = 6{\text{B}}{{\text{0}}_{13}}$ A1

METHOD 2

attempted repeated division by 13 M1

$871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2$ A1

$871 = {520_{13}}$ A1

$1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}$ A1

$1157 = 6{\text{B}}{{\text{0}}_{13}}$ A1

Note: Allow (11) for B only if brackets or equivalent are present.

(ii) $871 = 13 \times 67;{\text{ }}1157 = 13 \times 89$ (M1)

67 and 89 are primes (base 10) or they are co-prime A1

So $\gcd (871,{\text{ }}1157) = 13$ AG

Note: Must be done by hence not Euclid’s algorithm on 871 and 1157.

[7 marks]

let K be the set of possible remainders on division by n (M1)

then $K = \{ {\text{0, 1, 2, }} \ldots n - 1\} $ has n members A1

because $n < n + 1{\text{ }}\left( { = n(L)} \right)$ A1

by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained) R1

at least two members of L correspond to one member of K AG

[4 marks]

(i) form the appropriate linear combination of the equations: (M1)

$2a + b - c = 7x + 7z$ A1

$ = 7(x + z)$ R1

so 7 divides $2a + b - c$ AG

(ii) modulo 2, the equations become M1

$y + z = 1$

$z = 0$ A1

$x = 1$

solution: (1, 1, 0) A1

Note: Award full mark to use of GDC (or done manually) to solve the system giving $x = - 1,{\text{ }}y = - 3,{\text{ }}z = 2$ and then converting mod 2.

[6 marks]

(i) separate consideration of even and odd n M1

${\text{eve}}{{\text{n}}^2} - {\text{even}} + {\text{odd is odd}}$ A1

${\text{od}}{{\text{d}}^2} - {\text{odd}} + {\text{odd is odd}}$ A1

all elements of P are odd AG

Note: Allow other methods eg, ${n^2} - n = n(n - 1)$ which must be even.

(ii) the list is [41, 41, 43, 47, 53, 61] A1

(iii) ${41^2} - 41 + 41 = {41^2}$ divisible by 41 A1

but is not a prime R1

the statement is disproved (by counterexample) AG

[6 marks]

Examiners report

[N/A]

One version of Fermat’s little theorem states that, under certain conditions, ${a^{p - 1}} \equiv 1(\bmod p)$ .

(i) Show that this result is not true when a = 2, p = 9 and state which of the conditions is not satisfied.

(ii) Find the smallest positive value of k satisfying the congruence ${2^{45}} \equiv k(\bmod 9)$ .

[6]

Find all the integers between 100 and 200 satisfying the simultaneous congruences $3x \equiv 4(\bmod 5)$ and $5x \equiv 6(\bmod 7)$ .

[6]

Markscheme

(i) ${2^8} = 256 \equiv 4(\bmod 9)$ (so not true) A1

9 is not prime A1

(ii) consider various powers of 2, e.g. obtaining M1

${2^6} = 64 \equiv 1(\bmod 9)$ A1

therefore

${2^{45}} = {({2^6})^7} \times {2^3}$ M1

$ \equiv 8(\bmod 9){\text{ (so }}k = 8)$ A1

[6 marks]

EITHER

the solutions to $3x \equiv 4(\bmod 5)$ are 3, 8, 13, 18, 23,… M1A1

the solutions to $5x \equiv 6(\bmod 7)$ are 4, 11, 18,… A1

18 is therefore the smallest solution A1

the general solution is

$18 + 35n{\text{ , }}n \in \mathbb{Z}$ M1

the required solutions are therefore 123, 158, 193 A1

$3x \equiv 4(\bmod 5) \Rightarrow 2 \times 3x \equiv 2 \times 4(\bmod 5) \Rightarrow x \equiv 3(\bmod 5)$ A1

$ \Rightarrow x = 3 + 5t$ M1

$ \Rightarrow 15 + 25t \equiv 6(\bmod 7) \Rightarrow 4t \equiv 5(\bmod 7) \Rightarrow 2 \times 4t \equiv 2 \times 5(\bmod 7) \Rightarrow t \equiv 3(\bmod 7)$ A1

$ \Rightarrow t = 3 + 7n$ A1

$ \Rightarrow x = 3 + 5(3 + 7n) = 18 + 35n$ M1

the required solutions are therefore 123, 158, 193 A1

using the Chinese remainder theorem formula method

first convert the congruences to $x \equiv 3(\bmod 5)$ and $x \equiv 4(\bmod 7)$ A1A1

$M = 35{\text{, }}{M_1} = 7{\text{, }}{M_2} = 5{\text{, }}{m_1} = 5,{\text{ }}{m_2} = 7,{\text{ }}{a_1} = 3,{\text{ }}{a_2} = 4$

${x_1}$ is the solution of ${M_2}{x_2} \equiv 1(\bmod {m_1})$ , i.e. $7{x_1} \equiv 1(\bmod 5)$ so ${x_1} = 3$

${x_2}$ is the solution of ${M_2}{x_2} \equiv 1(\bmod {m_2})$ , i.e. $5{x_2} \equiv 1(\bmod 7)$ so ${x_2} = 3$

a solution is therefore

$x = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2}$ M1

$ = 3 \times 7 \times 3 + 4 \times 5 \times 3 = 123$ A1

the general solution is $123 + 35n$ , $n \in \mathbb{Z}$ M1

the required solutions are therefore 123, 158, 193 A1

[6 marks]

Examiners report

[N/A]

A simple connected planar graph, has $e$ edges, $v$ vertices and $f$ faces.

(i) Show that $2e \ge 3f{\text{ if }}v > 2$.

(ii) Hence show that ${K_5}$, the complete graph on five vertices, is not planar.

[6]

(i) State the handshaking lemma.

(ii) Determine the value of $f$, if each vertex has degree $2$.

[4]

Draw an example of a simple connected planar graph on $6$ vertices each of degree $3$.

[2]

Markscheme

(i) METHOD 1

attempting to use $f = e - v + 2$ and $e \le 3v - 6$ (if $v > 2$) (M1)

$2e \le 6v - 12 = 6(e - f + 2) - 12$ M1A1

leading to $2e \ge 3f$ AG

METHOD 2

each face is bounded by at least three edges A1

Note: Award A1 for stating $e \ge 3f$.

each edge either separates two faces or, if an edge is interior to a face, it gets counted twice R1

Note: Award R1 for stating that each edge contributes two to the sum of the degrees of the faces (or equivalent) ie, $\sum {\deg (F) = 2e} $.

adding up the edges around each face R1

leading to $2e \ge 3f$ AG

(ii) ${K_5}$ has $e = 10$ A1

if the graph is planar, $f = 7$ A1

this contradicts the inequality obtained above R1

hence the graph is non-planar AG

[6 marks]

(i) the sum of the vertex degrees $ = 2e$ (or is even) or equivalent A1

(ii) if each vertex has degree $2$, then $2v = 2e$ A1

substituting $v = e$ into Euler’s formula M1

$f = 2$ A1

[4 marks]

for example,

[2 marks]

Total [12 marks]

Examiners report

In part (a) (i), many candidates tried to prove $2e \ge 3f$ with numerical examples. Only a few candidates were able to prove this inequality correctly. In part (a) (ii), most candidates knew that ${K_5}$ has 10 edges. However, a number of candidates simply drew a diagram with any number of faces and used this particular representation as a basis for their 'proof'. Many candidates did not recognise the 'hence' requirement in part (a) (ii).

In part (b) (i), many candidates stated the 'handshaking lemma' incorrectly by relating it to the 'handshake problem'. In part (b) (ii), only a few candidates determined that $v = e$ and hence found that $f = 2$.

In part (c), a reasonable number of candidates were able to draw a simple connected planar graph on $6$ vertices each of degree $3$. The most common error here was to produce a graph that contained a multiple edge(s).

The weights of the edges of a graph $H$ are given in the following table.

(i) Draw the weighted graph $H$.

(ii) Use Kruskal’s algorithm to find the minimum spanning tree of $H$. Your solution should indicate the order in which the edges are added.

(iii) State the weight of the minimum spanning tree.

[8]

Consider the following weighted graph.

(i) Write down a solution to the Chinese postman problem for this graph.

(ii) Calculate the total weight of the solution.

[3]

(i) State the travelling salesman problem.

(ii) Explain why there is no solution to the travelling salesman problem for this graph.

[3]

Markscheme

(i) A2

Note: Award A1 if one edge is missing. Award A1 if the edge weights are not labelled.

(ii) the edges are added in the order:

$FG{\rm{ }}1$ M1A1

$CE{\rm{ }}2$ A1

$ED{\rm{ }}3$

$EG{\rm{ }}4$ A1

$AC{\rm{ }}4$

Note: $EG$ and $AC$ can be added in either order.

(Reject $EF$)

(Reject $CD$)

$EB5$ OR $AB5$ A1

Notes: The minimum spanning tree does not have to be seen.

If only a tree is seen, the order by which edges are added must be clearly indicated.

(iii) $19$ A1

[8 marks]

(i) eg, $PQRSRTSTQP$ OR $PQTSTRSRQP$ M1A1

Note: Award M1 if in either (i) or (ii), it is recognised that edge $PQ$ is needed twice.

(ii) total weight $ = 34$ A1

[3 marks]

(i) to determine a cycle where each vertex is visited once only (Hamiltonian cycle) A1

of least total weight A1

(ii) EITHER

to reach $P$, $Q$ must be visited twice which contradicts the definition of the $TSP$ R1

the graph is not a complete graph and hence there is no solution to the $TSP$ R1

[3 marks]

Total [14 marks]

Examiners report

Part (a) was generally very well answered. Most candidates were able to correctly sketch the graph of $H$ and apply Kruskal’s algorithm to determine the minimum spanning tree of $H$. A few candidates used Prim's algorithm (which is no longer part of the syllabus).

Most candidates understood the Chinese Postman Problem in part (b) and knew to add the weight of $PQ$ to the total weight of $H$. Some candidates, however, did not specify a solution to the Chinese Postman Problem while other candidates missed the fact that a return to the initial vertex is required.

In part (c), many candidates had trouble succinctly stating the Travelling Salesman Problem. Many candidates used an ‘edge’ argument rather than simply stating that the Travelling Salesman Problem could not be solved because to reach vertex $P$, vertex $Q$ had to be visited twice.

Show that there are exactly two solutions to the equation $1982 = 36a + 74b$, with $a,{\text{ }}b \in \mathbb{N}$.

[8]

Hence, or otherwise, find the remainder when ${1982^{1982}}$ is divided by $37$.

[5]

Markscheme

$74 = 2 \times 36 + 2$ OR $\gcd (36,{\text{ }}74) = 2$ (A1)

$2 = ( - 2)(36) + (1)(74)$ M1

$1982 = ( - 1982)(36) + (991)(74)$ A1

so solutions are $a = - 1982 + 37t$ and $b = 991 - 18t$ M1A1

$a,{\text{ }}b \in \mathbb{N}{\text{ so }}\frac{{1982}}{{37}} \le t \le \frac{{991}}{{18}}\;\;\;{\text{(}}15.56 \ldots \le t \le 55.055 \ldots )$ (M1)(A1)

$t$ can take values $54$ or $55$ only A1AG

(Or the solutions are $(16,{\text{ }}19)$ or $(53,{\text{ }}1)$)

Note: Accept arguments from one solution of increasing/decreasing $a$ by $37$ and increasing/decreasing $b$ by $18$ to give the only possible positive solutions.

[8 marks]

$1982 = 53 \times 36 + 74$

$1982 = 55 \times 36 + 2$ (M1)

${1982^{36}} \equiv 1(\bmod 37){\text{ }}({\text{by FLT}})$ (M1)

${1982^{1982}} = {1982^{36 \times 55 + 2}} \equiv {1982^2}(\bmod 37)$ (A1)

$ \equiv 34(\bmod 37)$ A1

so the remainder is $34$ A1

Note: $1982$ in the base can be replaced by $21$.

Note: Award the first (M1) if the $1982$ in the experiment is correctly broken down to a smaller number.

[5 marks]

Total [13 marks]

Examiners report

[N/A]

(a) Using Fermat’s little theorem, show that, in base 10, the last digit of n is always equal to the last digit of ${n^5}$ .

(b) Show that this result is also true in base 30.

Markscheme

(a) using Fermat’s little theorem ${n^5} \equiv n(\bmod 5)$ (M1)

${n^5} - n \equiv 0(\bmod 5)$ A1

now ${n^5} - n = n({n^4} - 1)$ (M1)

$ = n({n^2} - 1)({n^2} + 1)$

$ = n(n - 1)(n + 1)({n^2} + 1)$ A1

hence one of the first two factors must be even R1

i.e. ${n^5} - n \equiv 0(\bmod 2)$

thus ${n^5} - n$ is divisible by 5 and 2

hence it is divisible by 10 R1

in base 10, since ${n^5} - n$ is divisible by 10, then ${n^5} - n$ must end in zero and hence ${n^5}$ and n must end with the same digit R1

[7 marks]

(b) consider ${n^5} - n = n(n - 1)(n + 1)({n^2} + 1)$

this is divisible by 3 since the first three factors are consecutive integers R1

hence ${n^5} - n$ is divisible by 3, 5 and 2 and therefore divisible by 30

in base 30, since ${n^5} - n$ is divisible by 30, then ${n^5} - n$ must end in zero and hence ${n^5}$ and n must end with the same digit R1

[2 marks]

Total [9 marks]

Examiners report

There were very few fully correct answers. If Fermat‟s little theorem was known, it was not well applied.

Write 57128 as a product of primes.

[4]

Prove that $\left. {22} \right|{5^{11}} + {17^{11}}$.

[4]

Markscheme

$457\,128 = 2 \times 228\,564$

$228\,564 = 2 \times 114\,282$

$114\,282 = 2 \times 57\,141$

$57\,141 = 3 \times 19\,047$

$19\,047 = 3 \times 6349$

$6349 = 7 \times 907$ M1A1

trial division by 11, 13, 17, 19, 23 and 29 shows that 907 is prime R1

therefore $457\,128 = {2^3} \times {3^2} \times 7 \times 907$ A1

[4 marks]

by a corollary to Fermat’s Last Theorem

${5^{11}} \equiv 5(\bmod 11){\text{ and }}{17^{11}} \equiv 17(\bmod 11)$ M1A1

${5^{11}} + {17^{11}} \equiv 5 + 17 \equiv 0(\bmod 11)$ A1

this combined with the evenness of LHS implies $\left. {25} \right|{5^{11}} + {17^{11}}$ R1AG

[4 marks]

Examiners report

Some candidates were obviously not sure what was meant by ‘product of primes’ which surprised the examiner.

There were some reasonable attempts at part (c) using powers rather than Fermat’s little theorem.

The diagram below shows the graph G with vertices A, B, C, D, E and F.

(i) Determine if any Hamiltonian cycles exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for a Hamiltonian cycle to exist.

(ii) Determine if any Eulerian circuits exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for an Eulerian circuit to exist.

Markscheme

(i) any Hamiltonian circuit ACBEFDA A2

(ii) no Eulerian circuit exists because the graph contains vertices of odd degree A2

[4 marks]

Examiners report

Parts (a) and (b) were well answered by many candidates. In (c), candidates who tried to prove the result by adding edges to a drawing of G were given no credit. Candidates should be aware that the use of the word ‘Prove’ indicates that a formal treatment is required Solutions to (d) were often disappointing although a graphical solution was allowed here.

The following diagram shows a weighted graph.

(a) Use Kruskal’s algorithm to find a minimum spanning tree, clearly showing the order in which the edges are added.

(b) Sketch the minimum spanning tree found, and write down its weight.

Markscheme

(a) use Kruskal’s algorithm: begin by choosing the shortest edge and then select a sequence of edges of non-decreasing weights, checking at each stage that no cycle is completed (M1)

choice	edge	weight
1	BG	1
2	AG	2
3	FG	3
4	BC	4
5	DE	5
6	AH	6
7	EG	7

Note: A1 for steps 2–4, A1for step 5 and A1for steps 6, 7.

Award marks only if it is clear that Kruskal’s algorithm is being used.

[5 marks]

(b) weight $ = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ A1

Note: Award FT only if it is a spanning tree.

[2 marks]

Examiners report

Well answered by the majority of candidates.

Let G be a simple, connected, planar graph.

(a) (i) Show that Euler’s relation $f - e + v = 2$ is valid for a spanning tree of G.

(ii) By considering the effect of adding an edge on the values of f, e and v show that Euler’s relation remains true.

(b) Show that K₅ is not planar.

Markscheme

(a) (i) A spanning tree with v vertices and (v −1) edges where f = 1 A1A1

f − e + v =1 − (v − 1) + v = 2 M1

So the formula is true for the tree AG

(ii) Adding one edge connects two different vertices, and hence an extra face is created M1R1

This leaves v unchanged but increases both e and f by 1 leaving f − e + v unchanged. Hence f − e + v = 2 . R1R1

[7 marks]

(b) Using $e \leqslant 3v - 6$ , M1

for ${K_5},{\text{ }}v = 5$ and $e = \left( {\begin{array}{*{20}{c}}
5 \\
2
\end{array}} \right) = 10$ A1A1

but 3v − 6 = 3(5) − 6 = 9 A1

9 is not greater or equal to 10 so ${K_5}$ is not planar R1

[5 marks]

Total [12 marks]

Examiners report

Part (a)(i) was done successfully but many students did not read part(ii) carefully. It said ‘adding an edge’ nothing else. Many candidates assumed it was necessary to add a vertex when this was not the case.

Part (b) was not found to be beyond many candidates if they used the inequality $e \leqslant 3v - 6$

(a) Write down Fermat’s little theorem.

(b) In base 5 the representation of a natural number X is ${\left( {k00013(5 - k)} \right)_5}$.

This means that $X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 - k)$.

In base 7 the representation of X is ${({a_n}{a_{n - 1}} \ldots {a_2}{a_1}{a_0})_7}$.

Find ${a_0}$.

Markscheme

(a) EITHER

if p is a prime ${a^p} \equiv a(\bmod p)$ A1A1

if p is a prime and $a$ $0(\bmod p)$ then ${a^{p - 1}} \equiv 1(\bmod p)$ A1A1

Note: Award A1 for p being prime and A1 for the congruence.

[2 marks]

(b) ${a_0} \equiv X(\bmod 7)$ M1

$X = k \times {5^6} + 25 + 15 + 5 - k$

by Fermat ${5^6} \equiv 1(\bmod 7)$ R1

$X = k + 45 - k(\bmod 7)$ (M1)

$X = 3(\bmod 7)$ A1

${a_0} = 3$ A1

[5 marks]

EITHER

$X - {7^5} = 14\,486$ (M1)

$X - {7^5} - 6 \times {7^4} = 80$

$X - {7^5} - 6 \times {7^4} - {7^2} = 31$

$X - {7^5} - 6 \times {7^4} - {7^2} - 4 \times 7 = 3$

$X = {7^5} + 6 \times {7^4} + {7^2} + 4 \times 7 + 3$ (A1)

$X = {(160\,143)_7}$ A1

$31\,293 = 7 \times 4470 + 3$ (M1)

$4470 = 7 \times 638 + 4$

$638 = 7 \times 91 + 1$

$91 = 7 \times 13 + 0$

$13 = 7 \times 1 + 6$ (A1)

$X = {(160\,143)_7}$ A1

[4 marks]

Total [11 marks]

Examiners report

Fermat’s little theorem was reasonably well known. Not all candidates took the hint to use this in the next part and this part was not done well. Part (c) could and was done even if part (b) was not.

(a) Show that, for a connected planar graph,

\[v + f - e = 2.\]

(b) Assuming that $v \geqslant 3$, explain why, for a simple connected planar graph, $3f \leqslant 2e$ and hence deduce that $e \leqslant 3v - 6$.

(c) The graph G and its complement ${G'}$ are simple connected graphs, each having 12 vertices. Show that ${G}$ and ${G'}$ cannot both be planar.

Markscheme

(a) start with a graph consisting of just a single vertex M1

for this graph, v = 1, f = 1 and e = 0, the relation is satisfied A1

Note: Allow solutions that begin with 2 vertices and 1 edge.

to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + f – e remains equal to 2 M1A1

or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + f – e remains equal to 2 M1A1

therefore, however we build up the graph, the relation remains valid R1

[7 marks]

(b) since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face R1

the factor 2 follows from the fact that every edge bounds (at most) 2 faces R1

hence $3f \leqslant 2e$ AG

from the Euler relation, $3f = 6 + 3e - 3v$ M1

substitute in the inequality, $6 + 3e - 3v \leqslant 2e$ A1

hence $e \leqslant 3v - 6$ AG

[4 marks]

since G and ${G'}$ have a total of $\left( {\begin{array}{*{20}{c}}
{12} \\
2
\end{array}} \right) = 66$ edges A1

it follows that ${G'}$ has 66 – e edges A1

for planarity we require

$e \leqslant 3 \times 12 - 6 = 30$ M1A1

and $66 - e \leqslant 30 \Rightarrow e \geqslant 36$ A1

these two inequalities cannot both be met indicating that both graphs cannot be planar R1

[7 marks]

Total [18 marks]

Examiners report

Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.

State Fermat’s little theorem.

Markscheme

if p is a prime (and $a \equiv 0(\bmod p)$ with $a \in \mathbb{Z}$) then A1

${a^{p - 1}} \equiv 1(\bmod p)$ A1

[2 marks]

Note: Accept ${a^p} \equiv a(\bmod p)$ .

Examiners report

Fermat’s little theorem was reasonably well known. Some candidates forgot to mention that p was a prime. Not all candidates took the hint to use this in the next part.

The positive integer p is an odd prime number.

Show that $\sum\limits_{k = 1}^p {{k^p} \equiv 0(\bmod p)} $.

[4]

Given that $\sum\limits_{k = 1}^p {{k^{p - 1}} \equiv n(\bmod p)} $ where $0 \leqslant n \leqslant p - 1$, find the value of n.

[4]

Markscheme

using Fermat’s little theorem,

${k^p} \equiv k(\bmod p)$ (M1)

therefore,

$\sum\limits_{k = 1}^p {{k^p} \equiv } \sum\limits_{k = 1}^p {k(\bmod p)} $ M1

$ \equiv \frac{{p(p + 1)}}{2}(\bmod p)$ A1

$ \equiv 0(\bmod p)$ AG

since $\frac{{(p + 1)}}{2}$ is an integer (so that the right-hand side is a multiple of p) R1

[4 marks]

using the alternative form of Fermat’s little theorem,

${k^{p - 1}} \equiv 1(\bmod p),{\text{ }}1 \leqslant k \leqslant p - 1$ A1

${k^{p - 1}} \equiv 0(\bmod p),{\text{ }}k = p$ A1

therefore,

$\sum\limits_{k = 1}^p {{k^{p - 1}} \equiv } \sum\limits_{k = 1}^{p - 1} {1{\text{ }}( + 0)(\bmod p)} $ M1

$ \equiv p - 1(\bmod p)$ A1

(so n = p − 1)

Note: Allow first A1 even if qualification on k is not given.

[4 marks]

Examiners report

Only the top candidates were able to produce logically, well thought-out proofs. Too many candidates struggled with the summation notation and were not able to apply Fermat’s little theorem. There was poor logic i.e. looking at a particular example and poor algebra.

(a) Use the Euclidean algorithm to find the gcd of 324 and 129.

(b) Hence show that $324x + 129y = 12$ has a solution and find both a particular solution and the general solution.

Markscheme

(a) $324 = 2 \times 129 + 66$ M1

$129 = 1 \times 66 + 63$

$66 = 1 \times 63 + 3$ A1

hence gcd (324, 129) = 3 A1

[3 marks]

(b) METHOD 1

Since $\left. 3 \right|12$ the equation has a solution M1

$3 = 1 \times 66 - 1 \times 63$ M1

$3 = - 1 \times 129 + 2 \times 66$

$3 = 2 \times (324 - 2 \times 129) - 129$

$3 = 2 \times 324 - 5 \times 129$ A1

$12 = 8 \times 324 - 20 \times 129$ A1

$(x,\,y) = (8,\, - 20)$ is a particular solution A1

Note: A calculator solution may gain M1M1A0A0A1.

A general solution is $x = 8 + \frac{{129}}{3}t = 8 + 43t,{\text{ }}y = - 20 - 108t,{\text{ }}t \in \mathbb{Z}$ A1

METHOD 2

$324x + 129y = 12$

$108x + 43y = 4$ A1

$108x \equiv 4(\bmod 43) \Rightarrow 27x \equiv 1(\bmod 43)$ A1

$x = 8 + 43t$ A1

$108(8 + 43t) + 43y = 4$ M1

$864 + 4644t + 43y = 4$

$43y = - 860 - 4644t$

$y = - 20 - 108t$ A1

a particular solution (for example $t = 0$) is $(x,\,y) = (8,\, - 20)$ A1

[6 marks]

The left side is even and the right side is odd so there are no solutions M1R1AG

[2 marks]

$\gcd (82,\,140) = 2$ A1

2 does not divide 3 therefore no solutions R1AG

[2 marks]

Total [11 marks]

Examiners report

This problem was not difficult but presenting a clear solution and doing part (b) alongside part (a) in two columns was. The simple answer to part (c) was often overlooked.

The weights of the edges of a graph G with vertices A, B, C, D and E are given in the following table.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for G .

[4]

(i) Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph obtained by removing the vertex A from G .

(ii) Hence use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for G .

[8]

Markscheme

using the nearest neighbour algorithm, starting with A,

${\text{A}} \to {\text{E, E}} \to {\text{C}}$ A1

${\text{C}} \to {\text{D, D}} \to {\text{B}}$ A1

${\text{B}} \to {\text{A}}$ A1

the upper bound is therefore 9 + 10 + 16 + 13 + 11 = 59 A1

[4 marks]

(i) the edges are added in the order CE A1

BD A1

BE A1

(ii) the weight of the minimum spanning tree is 37 (A1)

we now reconnect A with the 2 edges of least weight (M1)

i.e. AE and AB A1

the lower bound is therefore 37 + 9 + 11 = 57 A1

[8 marks]

Examiners report

[N/A]

The graph G has adjacency matrix M given below.

Draw the graph G .

[2]

What information about G is contained in the diagonal elements of M$^2$ ?

[1]

List the trails of length 4 starting at A and ending at C.

[3]

Markscheme

Note: Award A1 if only one error, A0 for two or more.

[2 marks]

the (k, k) element of M$^2$ is the number of vertices directly connected to vertex k A1

Note: Accept comment about the number of walks of length 2, in which the initial and final vertices coincide.

[1 mark]

the trails of length 4 are ABEDC, AFEDC, AFEBC A1A1A1

Note: A1A1A1 for three correct with no additions; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.

[3 marks]

Examiners report

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

Show that a graph is bipartite if and only if it contains only cycles of even length.

Markscheme

Suppose the graph is bipartite so that the vertices belong to one of two disjoint sets M, N. M1

Then consider any vertex V in M. To generate a cycle returning to V, we must go to a vertex in N, then to a vertex in M, then to a vertex in N, then to a vertex in M, etc. R1

To return to V, therefore, which belongs to M, an even number of steps will be required. R1

Now suppose the graph contains only cycles of even length. M1

Starting at any vertex V, define the set M as containing those vertices accessible from V in an even number of steps and the set N as containing those vertices accessible from V in an odd number of steps. R1

Suppose that the vertex X belongs to both M and N. Then consider the closed walk from V to X one way and back to V the other way. This closed walk will be of odd length. This closed walk can be contracted to a cycle which will also be of odd length, giving a contradiction to the initial assumption. R1

There can therefore be no vertices common to M and N which shows that the vertices can be divided into two disjoint sets and the graph is bipartite. R1

Consider any edge joining P to vertex Q. Then either ${\text{P}} \in {\text{M}}$ in which case ${\text{Q}} \in {\text{M}}$ or vice versa. In either case an edge always joins a vertex in M to a vertex in N so the graph is bipartite. R1

[8 marks]

Examiners report

Many candidates made a reasonable attempt at showing that bipartite implies cycles of even length but few candidates even attempted the converse.

The weighted graph H is shown below.

Use Kruskal’s Algorithm, indicating the order in which the edges are added, to find and draw the minimum spanning tree for H.

[6]

(i) A tree has v vertices. State the number of edges in the tree, justifying your answer.

(ii) We will call a graph with v vertices a “forest” if it consists of c components each of which is a tree.

Here is an example of a forest with 4 components.

How many edges will a forest with v vertices and c components have?

[5]

Markscheme

The edges are included in the order

CF A1

EF A1

BC A1

CD A1

AB A1

[6 marks]

(i) A tree with v vertices has v −1 edges. A1

Using v + f = e + 2 with f = 1, the result follows. R1

(ii) Each of the c trees will have one less edge than the number of vertices. R1

Thus the forest will have v − c edges. A2

[5 marks]

Examiners report

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result.

The graph G has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}
{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
{\text{A}}& {\text{ - }}&9&{\text{ - }}&8&4 \\
{\text{B}}& 9&{\text{ - }}&7&{\text{ - }}&2 \\
{\text{C}}& {\text{ - }}&7&{\text{ - }}&7&3 \\
{\text{D}}& 8&{\text{ - }}&7&{\text{ - }}&5 \\
{\text{E}}& 4&2&3&5&{\text{ - }}
\end{array}\]

Draw G in a planar form.

[2]

Giving a reason, determine the maximum number of edges that could be added to G while keeping the graph both simple and planar.

[4]

List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.

[10]

Markscheme

[2 marks]

For a simple planar graph containing triangles, $e \leqslant 3v - 6$ M1

Here $v = 5{\text{ , so }}e \leqslant 9$ . A1

There are already 8 edges so the maximum number of edges that could be added is 1. R1

This can be done e.g. AC or BD R1

[4 marks]

The distinct Hamiltonian cycles are

ABCDEA A2

ABCEDA A2

ABECDA A2

AEBCDA A2

Note: Do not penalise extra cycles.

The weights are 32, 32, 29, 28 respectively. A1

The Hamiltonian cycle of least weight is AEBCDA. R1

[10 marks]

Examiners report

A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

The complete graph H has the following cost adjacency matrix.

Consider the travelling salesman problem for H .

By first finding a minimum spanning tree on the subgraph of H formed by deleting vertex A and all edges connected to A, find a lower bound for this problem.

[5]

Find the total weight of the cycle ADCBEA.

[1]

What do you conclude from your results?

[1]

Markscheme

using any method, the minimum spanning tree is (M1)

Note: Accept MST = {BC, EC, DC} or {BC, EB, DC}

Note: In graph, line CE may be replaced by BE.

lower bound = weight of minimum spanning tree + 2 smallest weights connected to A (M1)

= 11 + 13 + 14 + 10 + 15 = 63 A1

[5 marks]

weight of ADCBEA = 10 + 14 + 11 + 13 + 15 = 63 A1

[1 mark]

the conclusion is that ADCBEA gives a solution to the travelling salesman problem A1

[1 mark]

Examiners report

This question was generally well answered although some candidates failed to realise the significance of the equality of the upper and lower bounds.

Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The possible roads and the costs of building them are shown in the graph below. Each vertex represents a town, each edge represents a road and the weight of each edge is the cost of building that road. He needs to design the lowest cost road system that will connect the six towns.

(a) Name an algorithm which will allow Sameer to find the lowest cost road system.

(b) Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.

Markscheme

(a) EITHER

Prim’s algorithm A1

Kruskal’s algorithm A1

[1 mark]

(b) EITHER

using Prim’s algorithm, starting at A

lowest cost road system contains roads AC, CD, CF, FE and AB A1

cost is 20 A1

using Kruskal’s algorithm

lowest cost road system contains roads CD, CF, FE, AC and AB A1

cost is 20 A1

Note: Accept alternative correct solutions.

[7 marks]

Total [8 marks]

Examiners report

Most candidates were able to name an algorithm to find the lowest cost road system and then were able apply the algorithm. All but the weakest candidates were able to make a meaningful start to this question. In 1(b) some candidates lost marks by failing to indicate the order in which edges were added.

Consider the complete bipartite graph ${\kappa _{3,\,3}}$.

Draw ${\kappa _{3,\,3}}$.

[1]

a.i.

Show that ${\kappa _{3,\,3}}$ has a Hamiltonian cycle.

[1]

a.ii.

Draw ${\kappa _{3,\,2}}$ and explain why it does not have a Hamiltonian cycle.

[2]

a.iii.

In the context of graph theory, state the handshaking lemma.

[1]

b.i.

Hence show that a graph G with degree sequence 2, 3, 3, 4, 4, 5 cannot exist.

[2]

b.ii.

Let T be a tree with $v$ where $v$ ≥ 2.

Use the handshaking lemma to prove that T has at least two vertices of degree one.

[4]

Markscheme

[1 mark]

a.i.

for example ADBECFA A1

Note: Accept drawing the cycle on their diagram.

Note: Accept Dirac’s theorem (although it is not on the syllabus for (a)(ii). There is no converse that could be applied for (a)(iii).

[1 mark]

a.ii.

a Hamiltonian cycle would have to alternate between the two vertex subsets which is impossible as 2 ≠ 3 R1

Note: Award R1 for an attempt to construct a Hamiltonian cycle and an explanation of why it fails, eg, ADBEC but there is no route from C to A without re-using D or E so no cycle. There are other proofs eg, have to go in and out of A, similarly B and C giving all edges leading to a contradiction.

[2 marks]

a.iii.

the sum of the vertex degrees is twice the number of edges A1

[1 mark]

b.i.

assume G exists

the sum 2 + 3 + 3 + 4 + 4 + 5 = 21 A1

this is odd (not even) R1

this contradicts the handshaking lemma

so G does not exist AG

[2 marks]

b.ii.

T has $v - 1$ edges A1

EITHER

if $k$ vertices have degree 1 then $v - k$ vertices have degree ≥ 2 R1

by the handshaking lemma

$2v - 2 \geqslant 1 \times k + 2\left( {v - k} \right)\left( { = 2v - k} \right)$ M1

this gives $k$ ≥ 2 A1

let S be the sum of vertex degrees

consider T having either no or one vertex of degree 1 R1

case 1 suppose T has no vertices of degree 1 (eg, all vertices have degrees ≥ 2)

by the handshaking lemma

$S \geqslant 2v \ne 2\left( {v - 1} \right)$ (not possible) A1

case 2 suppose T has one vertex of degree 1 (eg, $v - 1$ vertices have degrees ≥ 2)

by the handshaking lemma

$S \geqslant 2\left( {v - 1} \right) + 1 \ne 2\left( {v - 1} \right)$ (not possible) A1

THEN

so T has at least two vertices of degree 1 AG

[4 marks]

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

a.iii.

[N/A]

b.i.

[N/A]

b.ii.

[N/A]

Draw the complement of the following graph as a planar graph.

[3]

A simple graph G has v vertices and e edges. The complement $G'$ of G has ${e'}$ edges.

(i) Prove that $e \leqslant \frac{1}{2}v(v - 1)$ .

(ii) Find an expression for $e + e'$ in terms of v .

(iii) Given that ${G'}$ is isomorphic to G , prove that v is of the form 4n or 4n + 1 for $n \in {\mathbb{Z}^ + }$ .

(iv) Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.

(v) Prove that if $v \geqslant 11$ , then G and ${G'}$ cannot both be planar.

[14]

Markscheme

as a first step, form the following graph

(M1)(A1)

make it planar

[3 marks]

(i) an edge joins a pair of vertices R1

there is a maximum of $\left( {\begin{array}{*{20}{c}}
v \\
2
\end{array}} \right) = \frac{1}{2}v(v - 1)$ possible unordered pairs of vertices, hence displayed result A1AG

(ii) an edge joins two vertices in ${G'}$ if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs R1

$e + e' = \frac{1}{2}v(v - 1)$ A1

(iii) the two graphs have the same number of edges R1

$ \Rightarrow e = \frac{1}{4}v(v - 1)$ A1

v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result A1AG

(iv) the required graphs have four vertices and three edges A1

if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa R1

if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph A1

state it is isomorphic to its complement A1 N2

Note: Alternative proofs are possible, but should include the final statement for full marks.

(v) using $e \leqslant 3v - 6$ for planar graphs M1

$\frac{1}{2}v(v - 1) = e + e' \leqslant 6v - 12$ A1

${v^2} - 13v + 24 \leqslant 0$ is not possible for $v \geqslant 11$ R1

[14 marks]

Examiners report

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

(a) A connected planar graph G has e edges and v vertices.

(i) Prove that $e \geqslant v - 1$.

(ii) Prove that e = v −1 if and only if G is a tree.

(b) A tree has k vertices of degree 1, two of degree 2, one of degree 3 and one of degree 4. Determine k and hence draw a tree that satisfies these conditions.

\[\left( {\begin{array}{*{20}{c}}
0&1&1&0&0&0 \\
1&0&0&1&1&0 \\
1&0&0&0&1&1 \\
0&1&0&0&0&0 \\
0&1&1&0&0&0 \\
0&0&1&0&0&0
\end{array}} \right)\]

(i) Explain why H cannot be a tree.

(ii) Draw the graph of H .

(d) Prove that a tree is a bipartite graph.

Markscheme

(a) (i) Euler’s relation is

$e = v - 2 + f \geqslant v - 1,{\text{ as }}f \geqslant 1$ M1A1

(ii) $G{\text{ is a tree }} \Leftrightarrow {\text{ no cycles }} \Leftrightarrow {\text{ }}f = 1$ R1R1

[4 marks]

(b) the result from (a) (ii) gives

$e = k + 2 + 1 + 1 - 1 = k + 3$ M1A1

for a tree we also have

$2e = {\text{sum of degrees}}$ M1

$2k + 6 = k + 4 + 3 + 4 = k + 11$

hence $k = 5$ A1

Note: Accept alternative correct solutions.

[6 marks]

G cannot be a tree AG

(ii) A1

[3 marks]

(d) take any vertex in the tree and colour it black M1

colour all adjacent vertices white

colour all vertices adjacent to a white vertex black

continue this procedure until all vertices are coloured M1

which must happen since the graph is connected R1

as the tree contains no cycles, no vertex can be both black and white and the graph is proved to be bipartite R1

[4 marks]

Total [17 marks]

Examiners report

Many candidates seem only to have a weak understanding of the requirements for the proof of a mathematical statement.

The diagram below shows the weighted graph G .

(a) (i) What feature of the graph enables you to deduce that G contains an Eulerian circuit?

(ii) Find an Eulerian circuit.

Markscheme

(a) (i) all the vertices have even degree A1

(ii) for example ABCDECFBEFA A2

[3 marks]

M1A1A1A1A1A1

Note: Award each A1 for the edge added in the correct order. Award no further marks after the first error.

[6 marks]

Total [9 marks]

Examiners report

Part (a) was well answered in general. Part (c) was well answered.

The graph G has vertices P , Q , R , S , T and the following table shows the number of edges joining each pair of vertices.

Draw the graph G as a planar graph.

[2]

Giving a reason, state whether or not G is

(i) simple;

(ii) connected;

(iii) bipartite.

[4]

Explain what feature of G enables you to state that it has an Eulerian trail and write down a trail.

[2]

Explain what feature of G enables you to state it does not have an Eulerian circuit.

[1]

Find the maximum number of edges that can be added to the graph G (not including any loops or further multiple edges) whilst still keeping it planar.

[4]

Markscheme

[2 marks]

(i) G is not simple because 2 edges join P to T R1

(ii) G is connected because there is a path joining every pair of vertices R1

(iii) (P, R) and (Q, S, T) are disjoint vertices R1

so G is bipartite A1

Note: Award the A1 only if the R1 is awarded.

[4 marks]

G has an Eulerian trail because it has two vertices of odd degree (R and T have degree 3), all the other vertices having even degree R1

the following example is such a trail

TPTRSPQR A1

[2 marks]

G has no Eulerian circuit because there are 2 vertices which have odd degree R1

[1 mark]

consider

so it is possible to add 3 extra edges A1

consider G with one of the edges PT deleted; this is a simple graph with 6 edges; on addition of the new edges, it will still be simple M1

$e \leqslant 3v - 6 \Rightarrow e \leqslant 3 \times 5 - 6 = 9$ R1

so at most 3 edges can be added R1

[4 marks]

Examiners report

[N/A]

(i) A graph is simple, planar and connected. Write down the inequality connecting v and e, and give the condition on v for this inequality to hold.

(ii) Sketch a simple, connected, planar graph with v = 2 where the inequality from part (b)(i) is not true.

(iii) Sketch a simple, connected, planar graph with v =1 where the inequality from part (b)(i) is not true.

(iv) Given a connected, planar graph with v vertices, ${v^2}$ edges and 8 faces, find v. Sketch a graph that fulfils all of these conditions.

Markscheme

(i) $e \leqslant 3v - 6,{\text{ for }}v \geqslant 3$ A1A1

(ii) A1

(iii) A1

(iv) from Euler’s relation $v - e + f = 2$

$v - {v^2} + 8 = 2$ M1

${v^2} - v - 6 = 0$ A1

$(v + 2)(v - 3) = 0$

$v = 3$ A1

for example

Note: There are many possible graphs.

[8 marks]

Examiners report

In (b) most candidates gave the required inequality although some just wrote down both inequalities from their formula booklet. The condition $v \geqslant 3$ was less well known but could be deduced from the next 2 graphs. Euler’s relation was used well to obtain the quadratic to solve and many candidates could then draw a correct graph.

The table below shows the distances between towns A, B, C, D and E.

(i) Draw the graph, in its planar form, that is represented by the table.

(ii) Write down with reasons whether or not it is possible to find an Eulerian trail in this graph.

(iii) Solve the Chinese postman problem with reference to this graph if A is to be the starting and finishing point. Write down the walk and determine the length of the walk.

[9]

Show that a graph cannot have exactly one vertex of odd degree.

[2]

Markscheme

(i)

A1A1A1

Note: Award A1 for the vertices, A1 for edges and A1 for planar form.

(ii) It is possible to find an Eulerian trail in this graph since exactly two of the vertices have odd degree R1

(iii) B and D are the odd vertices M1

$BC + CD = 3 + 2 = 5{\text{ and }}BD = 9,$ A1

since 5 < 9 , BC and CD must be traversed twice R1

A possible walk by inspection is ACBDABCDCEA A1

This gives a total length of

2(2 + 3) + 8 + 9 + 5 + 7 + 10 + 6 = 55 for the walk A1

[9 marks]

The sum of all the vertex degrees is twice the number of edges, i.e. an even number.

Hence a graph cannot have exactly one vertex of odd degree. M1R1

[2 marks]

Examiners report

Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.

A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.

Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.

A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.

A graph G with vertices A, B, C, D, E has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}
{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
{\text{A}}& - &{12}&{10}&{17}&{19} \\
{\text{B}}&{12}& - &{13}&{20}&{11} \\
{\text{C}}&{10}&{13}& - &{16}&{14} \\
{\text{D}}&{17}&{20}&{16}& - &{15} \\
{\text{E}}&{19}&{11}&{14}&{15}& -
\end{array}\]

(a) (i) Use Kruskal’s algorithm to find and draw the minimum spanning tree for G.

(ii) The graph H is formed from G by removing the vertex D and all the edges connected to D. Draw the minimum spanning tree for H and use it to find a lower bound for the travelling salesman problem for G.

(b) Show that 80 is an upper bound for this travelling salesman problem.

Markscheme

(a) (i) the edges are joined in the order

ED A2

Note: Final A1 independent of the previous A2.

(ii)

the weight of this spanning tree is 33 A1

to find a lower bound for the travelling salesman problem, we add to that the two smallest weights of edges to D, i.e. 15 +16, giving 64 M1A1

[7 marks]

(b) an upper bound is the weight of any Hamiltonian cycle, e.g. ABCDEA has weight 75 so 80 is certainly an upper bound M1A1

[2 marks]

Total [9 marks]

Examiners report

Part (a) was well done by many candidates although some candidates simply drew the minimum spanning tree in (i) without indicating the use of Kruskal’s Algorithm. It is important to stress to candidates that, as indicated in the rubric at the top of Page 2, answers must be supported by working and/or explanations. Part (b) caused problems for some candidates who obtained the unhelpful upper bound of 96 by doubling the weight of the minimum spanning tree. It is useful to note that the weight of any Hamiltonian cycle is an upper bound and in this case it was fairly easy to find such a cycle with weight less than or equal to 80.

Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and state its length.

[5]

Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph and state its length.

[7]

Markscheme

Kruskal’s algorithm gives the following edges

CD (4) M1A1

AD (5)

EF (7) A1

EA (8)

BC (11)

FG (12) A1 N0

length of the spanning tree is 47 A1

[5 marks]

for Dijkstra’s algorithm there are three things associated with a node: order; distance from the initial node as a permanent or temporary node M1

Note: Deduct A1 for each error or omission.

the shortest path is AFBCD A1

the length is 26 A1 N0

[7 marks]

Examiners report

Setting out clearly the steps of the algorithms is still a problem for many although getting the correct spanning tree and its length were not.

The adjacency table of the graph G , with vertices P, Q, R, S, T is given by:

(a) Draw the graph G .

(b) (i) Define an Eulerian circuit.

(ii) Write down an Eulerian circuit in G starting at P.

(ii) Explain why it is not possible to have a Hamiltonian cycle in G .

Markscheme

(a)

Note: Award A2 for one missing or misplaced edge,

A1 for two missing or misplaced edges.

[3 marks]

(b) (i) an Eulerian circuit is one that contains every edge of the graph exactly once A1

(ii) a possible Eulerian circuit is

${\text{P}} \to {\text{Q}} \to {\text{S}} \to {\text{P}} \to {\text{Q}} \to {\text{Q}} \to {\text{R}} \to {\text{T}} \to {\text{R}} \to {\text{R}} \to {\text{P}}$ A2

[3 marks]

exactly once A1

(ii) to pass through T, you must have come from R and must return to R. R3

hence there is no Hamiltonian cycle

[5 marks]

Examiners report

Stronger candidates had little problem with this question, but a significant number of weaker candidates started by making errors in drawing the graph G, where the most common error was the omission of the loops and double edges. They also had problems working with the concepts of Eulerian circuits and Hamiltonian cycles.

In the graph given above, the numbers shown represent the distance along that edge.

Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T . Write down this shortest path.

[6]

(i) Does this graph have an Eulerian circuit? Justify your answer.

(ii) Does this graph have an Eulerian trail? Justify your answer.

[4]

The graph above is now to be considered with the edges representing roads in a town and with the distances being the length of that road in kilometres. Huan is a postman and he has to travel along every road in the town to deliver letters to all the houses in that road. He has to start at the sorting office at S and also finish his route at S . Find the shortest total distance of such a route. Fully explain the reasoning behind your answer.

[4]

Markscheme

from tabular method as shown above (or equivalent) M1A1A1

Note: Award the first A1 for obtaining 3 as the shortest distance to C.

Award the second A1 for obtaining the rest of the shortest distances.

shortest path has length 17 A1

backtracking as shown above (or equivalent) (M1)

shortest path is SABT A1

[6 marks]

(i) no, as S and T have odd degree A1R1

Note: Mentioning one vertex of odd degree is sufficient.

(ii) yes, as only S and T have odd degree A1R1

Note: In each case only award the A1 if the R1 has been given.

Accept an actual trail in (b)(ii).

[4 marks]

Huan has to travel along all the edges via an open Eulerian trail of length R1

4 + 3 + 5 + 2 + 1 + 3 + 5 + 4 + 7 + 8 + 5 + 6 + 7 + 6 + 6 + 8 + 9 = 94 A1

and then back to S from T along the shortest path found in (a) of length 17 R1

so shortest total distance is 94 + 17 = 111 A1

[4 marks]

Examiners report

This was quite well answered. Some candidates did not make their method clear and others showed no method at all. Some clearly had a correct method but did not make it clear what their final answers were. It is recommended that teachers look at the tabular method with its backtracking system as shown in the mark scheme as an efficient way of tackling this type of problem.

Fairly good knowledge shown here but not by all.

Some good answers but too much confusion with methods they partly remembered about the travelling salesman problem. Candidates should be aware of helpful connections between parts of a question.

Consider the following weighted graph.

(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree. Indicate the order in which you select the edges and draw the final spanning tree.

(ii) Write down the total weight of this minimum spanning tree.

(b) Sketch a spanning tree of maximum total weight and write down its weight.

Markscheme

(a) (i) (Kruskal’s: successively take an edge of smallest weight without forming a cycle)

${1^{{\text{st}}}}$ edge DC (weight 1) A1

${2^{{\text{nd}}}}$ edge EG (weight 2) A1

${3^{{\text{rd}}}}$ edge DE (weight 3) A1

${4^{{\text{th}}}}$ edge EF (weight 6) A1

${5^{{\text{th}}}}$ edge AD (weight 7) A1

${6^{{\text{th}}}}$ edge AB (weight 8) A1

Notes: Weights are not required on the diagram.

Allow A2(d) if the (correct) edges are in the wrong order e.g. they have used Prim’s rather than Kruskal’s algorithm.

(ii) total weight is 1 + 2 + 3 + 6 + 7 + 8 = 27 A1

[8 marks]

(b) EITHER

Notes: Award A2 for five or four correct edges,

A1 for three or two correct edges

A0 otherwise.

Weights are not required on the diagram.

THEN

total weight is 6 + 7 + 7 + 8 + 9 + 10 = 47 A1

[4 marks]

Total [12 marks]

Examiners report

Good algorithm work was shown; sometimes there were mistakes in giving the order of the edges chosen by, for example doing Prim’s algorithm instead of Kruskal’s.

The vertices of a graph L are A, B, C, D, E, F, G and H. The weights of the edges in L are given in the following table.

Draw the graph L.

Markscheme

Note: Award A1 if one line missing or one line misplaced. Weights are not required.

[2 marks]

Examiners report

Most candidates were able to draw the graph as required in (a) and most made a meaningful start to applying Prim’s algorithm in (b). Candidates were not always clear about the order in which the edges were to be added.

In any graph, show that

(i) the sum of the degrees of all the vertices is even;

(ii) there is an even number of vertices of odd degree.

[5]

Consider the following graph, M.

(i) Show that M is planar.

(ii) Explain why M is not Eulerian.

(iii) By adding one edge to M it is possible to make it Eulerian. State which edge must be added.

This new graph is called N.

(iv) Starting at A, write down a possible Eulerian circuit for N.

(v) Define a Hamiltonian cycle. If possible, write down a Hamiltonian cycle for N, and if not possible, give a reason.

(vi) Write down the adjacency matrix for N.

(vii) Which pair of distinct vertices has exactly 30 walks of length 4 between them?

[12]

Markscheme

(i) When we sum over the degrees of all vertices, we count each edge twice. Hence every edge adds two to the sum. Hence the sum of the degrees of all the vertices is even. R2

(ii) divide the vertices into two sets, those with even degree and those with odd degree M1

let S be the sum of the degrees of the first set and let T be the sum of the degrees of the second set

we know S + T must be even

since S is the sum of even numbers, then it is even R1

hence T must be even R1

hence there must be an even number of vertices of odd degree AG

[5 marks]

(i)

(ii) the graph M is not Eulerian because vertices D and F are of odd degree A1

(iii) the edge which must be added is DF A1

(iv)

a possible Eulerian circuit is ABDFBCDEFGCA A2

Note: award A1 for a correct Eulerian circuit not starting and finishing at A.

(v) a Hamiltonian cycle is one that contains each vertex in N A1

with the exception of the starting and ending vertices, each vertex must only appear once A1

a possible Hamiltonian cycle is ACGFEDBA A1

(vi) $\left( {\begin{array}{*{20}{c}}
0&1&1&0&0&0&0 \\
1&0&1&1&0&1&0 \\
1&1&0&1&0&0&1 \\
0&1&1&0&1&1&0 \\
0&0&0&1&0&1&0 \\
0&1&0&1&1&0&1 \\
0&0&1&0&0&1&0
\end{array}} \right)$ A2

(vii) using adjacency matrix to power 4 (M1)

C and F A1

[12 marks]

Examiners report

Most candidates were able to start (a), but many found problems in expressing their ideas clearly in words. Stronger candidates had little problem with (b), but a significant number of weaker candidates had problems working with the concepts of Eulerian circuits and Hamiltonian cycles and with understanding how to find a specific number of walks of a certain length as required in (b) (vii).

\((1,{\text{ }}0)\)		\((0,{\text{ }}1)\)
		\( - 3(1,{\text{ }}0)\)
		\(( - 3,{\text{ }}1)\)

\( - ( - 3,{\text{ }}1)\)
\((4,{\text{ }} - 1)\)
		\( - 3(4,{\text{ }} - 1)\)
		\(( - 15,{\text{ }}4)\)